Medal of Honor Allied Assault... or if that isn't old school enough Doom.

Breathless. Spent many hours there.

And not to forget [url=http://www.lemonamiga.com/?game_id=1852 ]Genetic Species. [/url]

Well, I heard it being called a pure example of "oldschool" gameplay, so I consider it as such. I'm not that big on FPSs, so I could be mistaken. *shrugs*

Admittedly my experience in the genre is limited but I loved both Operation: Flashpoint (kind of an FPS) and BF 1942 + the expansions. Mods only made them better.

Yeah, people call it that, because it was an unrealistic, fast-paced shooter in an age of shooters striving for realism. In fact it's just as different from oldschool FPS games as those realistic shooters are / were.
Oh yes, Operation Flashpoint is just excellent. I wouldn't call it my favourite FPS per se, but I'd call it my favourite ... Well ... Simulation of war

Of "real" FPS'es I guess it must be Deus Ex.
I also have a soft spot for IGI 2: Covert Strike.

My favorite of all time is U. DOOM.

Single Player: Duke Nukem 3d

Multi Player: Unreal Tournament

For me specifically, it's pre-mouselook FPS games in true 3D. I really think that has to biggest change and the most jarring thing about retro-gaming old ones. I think that made buying, installing, and booting up "Blood" again (I originally played the shareware version to death in the bronze age) here on GOG unplayable to me. I played my fair share of Wolfenstein, Doom, Hexen, etc as a kid. But now I can't stand it; no mouselook drives me crazy.

For the OP's quesiton: American McGee's Alice. Dark whimsy, creativity, memorable characters, mind-burning level-design (which has aged better than other games of its vintage), and eccentric weaponry, which means you can't run through gunning everything down. I can still quote dialog from it.

Oh yeah, loved the IGI games too.

I played a fair bit of FPS' in the past hard to pick one so here are my fav(s):

System Shock
System Shock 2
Deus ex
Doom II
Rise of the Triad
Wolfenstein
Duke Nukem 3D

bold = in particular

Outlaws.

Blood
...
and Outlaws.
And maybe Unreal T.

DOOM 1 and DOOM 2.

The perfect balance between simplicity and complexity.

Based on what most of you guys have posted so far as being old school FPSs, I can't say I have played very many. I didn't like Wolfenstein, so that leaves Quake, Unreal, and Jedi Knight: Dark Forces 2 (this is off the top of my head; I've probably played more). I only played Quake recently, and I enjoyed it immensely (even more than Quake 2, despite liking that one as well). Despite only finishing Unreal with cheats (I was much younger), the whole setting left quite an impact on me for some reason.

Dark Forces 2 wins, though, not only because of nostalgia, but because I really enjoy it still today.