Why don't I have a custom title by now?!
What's the criteria for "actual storyline"?
So, my friend is pretty new to Doom and asked two questions:
1. Are there any Doom mods with an actual storyline?
While the places themselves can convey a story, the typical storyline in Doom mods is "this is another facility that has been overrun by demons and possessed zombies, clean it up, also you might have to go to Hell to show the demons how it feels to have people barging at home and killing everybody, see if they like them apples".
If "minimalist story in a readme and maybe if we're lucky some dehacked string replacement for the intermission text screens" isn't enough to qualify, if he wants a story that's presented during the game with messages and scripted events, then the choice is pretty much restricted to a subset ZDoom stuff (and some Legacy mods).
That said: definitely this and that. It's all story.
Kidding aside, Barista, Claustrophobia, Doom Resurrection, Eternal Doom 4, RTC-3057, Space Station Omega, and Void, among others.
For GZDoom, BGPA, The City of the Damned - Apocalypse, Cold as Hell, Legacy of Suffering, Paranoid, Stronghold, The Ultimate Torment and Torture, Unloved, and ZanZan which is very weird.
For Legacy, but works okay with GZDoom, High Tech Hell 2 (fun fact: there is no High Tech Hell 1).
(I wouldn't really recommend the Community is Falling and Massmouth mods. Even though they have storylines and stuff, and are partial-to-total conversions, they rely too much on oooooold in-jokes to be very attractive to a newbie.)
On the other hand, if storylines implied by the setting without having text cutscenes and stuff are okay, then there's just far too many stuff to list. I'll mention the recent releases of Lunatic and Reverie.
As far as partial-to-total conversions go, Harmony is very good while still offering a true-to-form Doom experience. Both Action Dooms are great, Urban Brawl being especially impressive. CQ3 is actually fun, despite the silliness. The Darkest Hour is good too. Star Wars Chibi Rebellion is worth a try, too. In more classic style, Aliens TC and Batman Doom.
2. What's the 'best' mod for Doom?
Now I know that "best" is pretty subjective, but what would you recommend to a guy who's pretty new to Doom? Before you mention brutaldoom, I've showed it to him and he loves it, but I think he's looking more towards partial/total conversions.
There's also a ton of excellent mods that aren't really conversions.
In that category, Scimitar. Short levels, well-made, can be seen as a partial conversion thanks to the dehacked work, doesn't become insanely hard contrarily to Scythe.
I don't play many conversions, but as far as add-ons go, I've recommended Perdition's Gate to newbies before. The levels are small and relatively simple--good material for the modern "run towards the spot the NPC told you to" FPS gamer.