Well, I'll assume you already have Half-Life from the whole "playing ESF" thing.
How about Half-Life 2, if you haven't already gotten/beaten it? I'd recommend a playthrough of that at least once.
The F.E.A.R demo was nice, so that might be a pretty good newer game to check out -- the only reason I didn't buy it is because I burned out on it through the demo's multiplayer. I heard the single-player was great, and I enjoyed the frantic pace of the multiplayer in the demo.
Was chatting it up with one of the programmers of Quake 4 during development, but I've heard that it needs a monster rig to run properly.
If you've got a mid-range system, Far Cry is very nice. Extremely nice. In fact, I'll finish this response after I play some Far Cry...
...I suddenly decided to wait.
Older games you might want to check out are Fallout 2 (it's ok to skip number one), System Shock 2 (again, "there was no prequel"), Star Wars Jedi Knight II: Jedi Outcast (Jedi Outcast II: Jedi Academy has far superior multiplayer, but weak single player, IMO), Warcraft III, or Planescape: Torment, if you're ok with reading *ungodly* amounts of text for one of the most engrossing fantasy stories you'll ever read. Erh, "play".
If you're into superheroes (who isn't?!), buy Freedom Force. Run, do not walk, to the store and buy this game if you don't already own it. It's got a story, the characters have character, and, hey, if you know Python, you can mod it out the wazoo. If you've already got it, check out The Strangers mod for it. You'll want to beat the original before you play it, because it doesn't start slow enough for newbies, but if you play the original unmodded game long enough to understand the combat flow, you'll be alright.
Warhammer 40K: Dawn of War was alright, I guess. It's a passable RTS that really seemed to sell on the level of gore (which is rather tasteful in-game) it contained, but the main strategy AFAICT is just camp->build troops->attack en masse. That's alright, but the game seems to be focused toward slower play than Warcraft III (which I'd been playing a lot before I found WH40K: DoW).
Guess that's it. After typing this reply, I'm curious as to whether or not you'll read it.