This is one game I am really looking forward to. Doom was awesome back in 1995 for the graphics and sheer fun factor, although this game will have to do a lot more if it is going to live up to the hype. The map design is something I consider particularly important, as I tend to spend some time exploring maps in detail in singleplayer FPS games, and Doom 3 is supposed to very good with that, although they say the game is a bit short. The price is higher than average but I always get games from ebay anyway, where they are much cheaper and still unused.
I think FPS games have been getting steadily better over the years. The graphics have always improved, level design and sound started getting dramatically better in the post-doom years and very recently the physics has also begun advancing. Moddability has also always been great in these games. The storylines haven't really gotten better with time, but there have always been a mix of excellent and crappy stories in games of any genre except maybe adventure games. The AI has improved immensely, although this is the one area where FPSs (and all games, for that matter) still leave something to be desired. UT2004 probably has the best I have seen but it's still a long way from a good human player. The standards are especially low in FPS games where the AI has to do things other than fighting (e.g. the Thief and Deus Ex series), although on the flip side this can lead to some comic effects.
A game does not have to be revolutionary to be great though, and there are games that are very innovative but still not good. FS and FS2 were hardly revolutionary; it was the heavy polish to the little things everywhere rather than major new ideas that made these games so good.
Also, how exactly is a game supposed to be scary? I never quite understood this. Immersive, sure, but scary? FPSs sometimes throw sudden and unexpected things at you, but you get used to it after a while, and some games really tend to overdo it. I always play games in pitch dark (monitor contrasts look nicer) and with headphones on but still have never come across anything genuinely scary.
Some comments on particular games:
I found Halo to be decent by PC standards but nothing special. It had an okay story and balanced gameplay but the level design was atrociously repetitive. My brother bought it though, so I don't care.

Half Life was a very good game but I personally didn't find it
that great compared to other FPSs around its time, such as Unreal and System Shock 2.
Deus Ex is unique in a way and is probably one of my favorite games ever, not only for the things usually talked about but also for the sheer amount of unintentional wackiness that can occur within the game's otherwise serious and realistic setting. I have spent as much time fooling around in that game as actually playing it and I have played through it at least ten times.
Also, does anyone here have Thief 3/deadly shadows? Is it good? (I have thief 2 and enjoyed that a lot) I would have already gotten this game but I think it uses the same engine as Deus Ex 2 and my biggest gripe with that game was its horribly unoptimized engine. Was it also simultaneously made for PC and xbox? That is what really killed DX2 in my opinion, although it still had some strong points.
Ace: The D1/D2 imps usually came in big bunches but they were really easy since they invariably hit each other accidentally, got mad and killed each other off. Do these guys come in large hordes in D3 as well? I doubt they would get angry like that this time around, but it might be possible to get them to kill each other by mistake.
