Play the Half-Life saga if you haven't, from the original, passing by Blue Shift and Opposing Force, followed by the sequel and both Episodes... now if only Black Mesa: Source could be released that would help (I.E. help convince relatively new comers to the H-L saga whom haven't played the original even once to finally experience it with relatively updated graphics, since that's exactly what turns off those new comers from even approaching the original with a kilometer-long stick).
If you did play them, then go for Quake, Quake II, then Quake IV why not. If you haven't played Prey I'd recommend it, pretty good single-player and decent multi-player (probably dead by now, but was decent about two years or so ago). If you feel like just shooting stuff without thinking and immersing your ears in some of the most immature dialog in recent video gaming history then go with Bulletstorm, or you could always give a try to Borderlands which is quite enjoyable in co-operation with people you know in real life (otherwise I wouldn't bother, with multi-player that is).
Here's a few others I can think of:
º Bioshock / Bioshock 2 (first is good, I liked it, I never played the 2nd myself)
º Serious Sam 1 / 2 [HD] / Serious Sam 3 (classics, I never played the latest one though)
º Duke Nukem Forever (heh... why not, if you can find it for like $5)
º RAGE (decent, not "bad", nothing mind-blowing, worth a go if you can find it cheap)
º F.E.A.R. 1 / 2 / 3 (I own the original, it was decent overall, good A.I. though)
º Portal 1 / 2 (first is good, second is much better, you should give the 2nd a try at least)
º Crysis / Warhead / Crysis 2 (first is good enough, Warhead has more action, I've played some of Crysis 2 on the 360 version at my counsin's place but I don't own it myself for PC, I thought it was decent, nothing much but decent nonetheless)
º Painkiller (the original and its expansion pack Battle out of Hell are quite fun, I wouldn't bother with the others though, it's very much in the veins of old-school shooting fun to burn some time, nothing else)
º Call of Duty series (the very first was excellent, the 2nd was great, the third is on the Wii, and the fourth is one of the most over-rated games in recent memory that I can think of, it wasn't "bad", just not as much as the press made it look like, after that I wouldn't bother)
º Battlefield series (1942 was superb and by now is perhaps a classic, Desert Combat gave birth to BF2 itself, I never played BF3 but I've seen it plenty of times, seems decent but probably not as fun as either 1942 or BF2, even 2142 seems better)
º Fallout 3 / New Vegas (I do consider them as first-person-shooters, there's a third-person perspective but the animations in 3rd person view are archaic to the extremes, I can't see anyone effectively playing the whole thing in 3rd person lest losing some, or a lot of your sanity but that's just me, other than that they were great games)
º S.T.A.K.L.E.R. trilogy (the first, in my humble opinion namely Shadow of Chernobyl is the best of the three thanks to its unequaled atmosphere)
º METRO 2033 (I've never played it myself, I've seen a lot of footage, supposedly in the veins of STALKER atmosphere-wise and perhaps context-wise being set in some post-apocalyptic environment, also supposedly very demanding and need a beefy PC to run at high settings)
º Cryostasis (relatively forgotten, those who played it to the end usually think it was quite decent, I never finished it myself but it's nothing bad, quite atmospheric and kind of surreal of a setting, I don't quite understand the story myself although I never could really pay much attention to it for some reason, I'll have to give it another go one day)
º Aliens VS Predator (2010 release, I've played it a bit myself... not really good in my book but then again I've played worse FPS games in the past, I guess that Colonial Marines will be better, at least I hope so)
º Left 4 dead / L4D2 (they're both multi-player focused, but not exclusively so, you can play all the maps in some sort of a chronological order of events in the short and simple story that it covers in doing so, it can be played as a single-player game, both of them, I do prefer the first myself thanks to a better more grittier and "serious" tone to it despite the inevitable humor from time to time, and L4D1's characters are more memorable, in my opinion, I own L4D2 I played it a bit and got bored of it before I made it to the end, I might continue one day)
º Mirror's Edge (I never played it myself, seen some footage, supposedly a sleeper hit and enjoyable, seems strange to me but than again I never played it, can't say much)
º Far Cry, FC2 (the first was and is still good, the 2nd has nothing to do with the first and was named FC2 probably only due to business reasons, the 2nd one can be either hated or appreciated, it's kinda both extremes, I myself couldn't stand the crazy repeated driving and malaria attacks, total game-play mechanics failures)
That's... pretty much what I can think of right now, I've surely forgotten a few especially the multi-player focused ones (such as Unreal Tournament and and so on). I hope that this list helps a bit.