I actually think that even with the modern focus on graphics, fairly complex level design could be retainable. The problem lies with what kalirion has suggested: To get the 'movie' feel of a videogame requires a ton of scripting, and scripting is just far easier if you can predict exact position of player at any given time.
Well System Shock came before that. And I'm sure there were more, even earlier examples.

Also, the focus has changed from "play the level" to "move through the story," and it's a little hard to execute Doom-like level design when your game is built around setpieces and very precise scripting.

I do really wish at least SOME shooters would remember how to do those sort of levels, though. Even supposedly retro games like Serious Sam and Painkiller are more like big arenas than levels.

Ultima Underworld :)

Technically the first would be one of the Catacombs games, I can't recall off the top of my head which one.

EDIT: Catacombs Apocalypse.

I find that map stupid. Because those are two different kind of games. It's like saying Coriolanus is a shitty comedy.

I like arcadish shooters, but I also like (some) of the story driven ones.

Hmm, I think you're correct, beat me by a year.

RPGs can do fantastic storytelling with open world. STALKER could do some good stories with open world, even tho it's not really such a good example (but that is not the fault of it's storytelling potential, more of a problem of scriptwriters.) It's not that hard to do open levels and interesting story progression, it just requires some experimentation, which studios are not willing to do nowadays it seems.

Final DOOM had great map design...

/me pouts

ಠ_ಠ

Also - I don't fancy running back and forth through a building and humping walls. That's not what I consider having a good time. I like the maps in the Left 4 Dead games, Clive Barker's Jericho or AvP2k. They are highly condensed doses of fun, which I consider superior to extensive mazes you run back and forth through in order to collect keycards, find "secrets", explore pointless dead-end sideway paths.

Lose the maze bullshit is all I can say. Whenever I load up a Wolfenstein or Hexen source port for some old school shooting I am usually turned off in mere moments by the maze bullshit. Right or wrong it's just not my thing (and wasn't back then either, which is why I rarely went beyond the shareware portions).

That said I do like some key/door shennanigans and more depth than merely pointing and shooting. Doom had a relatively good balance.

Yeah, mazes sucked. But they've had the right idea. I personally think that a game with one of the best level design I have ever played was the original System Shock (oh the shock!) it seemed that what they basically did was to design a space station, and then put some roadblocks around - many of which were avoidable via secret passages or you just got numerous directions that you could have taken. It was fantastic.

Other game I mostly liked was Duke Nukem 3D. It did have some maze crap and the button puzzles were utterly horrible, but you often got cities designed in a fairly logical manner, which allowed for exploration and some degree of freedom of movement. Same applies to Blood in most cases.

The only modern FPS games that seem beleivable in the way that levels are constructed are STALKER games, and perhaps Bioshock to some extent. Everything else is just plain weird - blocks of buildings where you only can enter a single door, entire city where a single road is free, etc.

I used to advocate mazes, but these days I've come to realize it's not about that. It's about putting interesting stuff into the levels, playing around with spaces, heights, teleporters, monster placements etc. Some of the most iconic maps in the Doom series and Blood aren't remembered for throwing you into one random corridor after another. Mazes are only a means of facilitating that. That being said, E1M2 is the only map to use mazes to make an impression without getting boring - IMO.

FEAR.

FPP shooters? First person pea shooters

Anyway i don't see any kind of design when i look at doom maps which consist of absolutely random mazelike corridors leading to a randomly put big rooms.