Depends whether we're counting Deus Ex and System Shock 2 as FPS or as FPS-RPGs. Deus Ex has strong rpg elements: non-combat skills (hacking, lockpicking, computers etc), choice+consequence, multiple solutions to tasks etc. System Shock 2 has hard skill requirements - can't wield a weapon without having sufficient points in the relevant skill, can't do decent damage without skillpoint investment, has psi-ops powers, major emphasis on scavenging materials and thriftness (using melee where possible to save on precious bullets), different skill trees (conventional weapons, energy weapons, melee, alien tech, hacking, repair, psi-ops etc) and rpg-style stats (str, agil, endurance, perception, intelligence, etc, which govern how high your skills can go). So I can see why you might put them as a different category of game. But if we're including them as FPSs, then they win hands down - even Bioshock was a generation behind them in gameplay despite coming out many years afterwards, and we're only just starting to catch back up to the games of that era now.
Otherwise, I'd probably say Halflife 1 - the sequel was fun as well, but there was something much more organic about the way the first one worked. Especially when after only a few hours of gameplay you reach the surface, thinking 'holy crap that game was short'...and then you realise that those marines aren't there to rescue you
. It helped that it was the first game to have decent AI, and the marines are the first time that the game shows it (until that point you've been fighting zombies, headcrabs and other aliens) - at the time you could expect to exploit a shooter's AI by hiding in a side-room and just blasting the enemies as they come around the corner (hell, you still CAN do that in most shooters) - it gave gamers a hell of a shock when the HL marines would just throw a couple of grenades into the room and be done with you.
