Thus, I am looking for something that you'd recommend a newbie to begin with.
A bit more information about how you play would be helpful. Alien Vendetta, for instance, is quite finishable by a mediocre player ... if you play on HMP, carrying gear across levels, and use lots of save and reload. If you play on UV, pistol start every level, and never save mid-level, then it's a very different story :)
It would also help to know if you like switch hunts and puzzles in your Doom. I personally don't, and due to that fact, I disliked Icarus enough that I never finished it. If you like that sort of thing, however, then it and Eternal Doom will be more to your liking than they were mine.
As a general rule, older megawads will have lower monster counts, and be easier overall than newer ones. On the other hand, they're more likely to have unintuitive level design decisions in them.
DTWID should be an excellent starting point for you - though new, it was consciously designed with a difficulty curve reminiscent of the original game.
The original Memento Mori shows its age in a number of ways, these days, but it was a landmark project for a reason - I thoroughly recommend playing it sooner rather than later (the longer you wait to play it, the more obvious its flaws will be).
You may also want to look at Interception. It's new, and the difficulty level might (or might not) prove too high, but it has the advantage of being the current megawad club project, which means several other people are playing it and you can compare notes with them about it in the dedicated thread.