Half Life, Half Life 2, Deus Ex, Deus Ex: Invisible War
Not really an FPS: Descent 1, 2 and 3, Wing Commander series, Wing Commander Privateer are also really good.
I still play the old Doom games on occasion. I'm not such a huge fan of the online FPS. I am not that good a player, and it gets really really tiring being killed every spawn cycle in Day of Defeat (about every 15s). Most of the time I have never seen the middle of the maps. No matter which side I play I always get killed near my spawn...
I like Deus Ex. It has really good integration of RPG and FPS elements. You can nearly go through the entire game without fighting if you're so inclined.
Thief 2 is another worthwile title to play.