Soldier of Fortune (2000) - no, the level design isn't the best, but the combat feels quite unlike anything else. Possibly the only FPS game in history where you wince every time you have to shoot someone, and feel less like a hero and more like a bit of a prick. No need to bother with the sequel, it's kind of shit.
No One Lives Forever (2000) - I've always had my criticisms of this one but it's undeniably a creative game with some superb ideas. Cate Archer rocks.
Gunman Chronicles (2000) - wonderfully creative GoldSrc game where you get a copyright-dodging diet-SHODAN as your new best pal. People sometimes write it off as a mere Half-Life mod, but that's not fair - there's a hell of a lot of good ideas here (the weird chemical gun with a trillion settings), and the setting and story are bizarre enough for a great time.
Serious Sam (2001) - I'll be honest, I can't distinguish between the first and second encounter, other than that TFE was desert and TSE was jungle. Still, these games are great when you get into the swing of them - they kind of suck but something about them just works when you're in the right mood. Probably the most exciting set of enemies since Doom.
Red Faction (2001) - Half-Life on Mars! Okay, not every part of the game works well, but few other FPS games of the era have such a thrilling range of ideas that they're willing to try out. From the SHIT disguise segments to the unique (albeit buggy) battle against the "suppression bot" to a tram chase to a trip into a low-gravity space station, Red Faction is just one idea after another. They don't all work, but who cares, we're having fun.
Gaylo (2001) - putting this on the list with a little bit of hesitation, but I do think it's still worth a playthrough these days. As a kid I never liked the spongey enemies and resented the console-first design, but when you get to grips with it there's a pretty sound game here, even if its reputation ended up being blown out of all proportion.
(I'm going to mention RTCW here - I'm not a massive fan of it, honestly, but people will ask "where's RTCW" if it's not mentioned. So here, RTCW.)
Medal of Honor: Allied Assault (2002) - do you like military shooters? Nah, me neither. Get past the dull WW2 trappings though and MoHAA is not bad for what it is. True, you're fighting the same enemy over and over and over again, but at least they try to give you a bit of level variety - from the infiltration of the u-boat pens to the sniper-ridden village to the tank segment. I think what helps MoHAA is that it's just a very professional, high-quality product, which makes a change from some other games of the era.
Iron Storm (2002) - might be the first one on this list some people haven't heard of. Hear me out - it's an alternate history where WW1 went on for-fucking-ever. Compared with MoHAA, Iron Storm is shovelware crap that barely functions. It is, however, very rich in ideas, and the devs really tried to make something unique and cool. Check it out.
Rainbow Six 3 (2003) - well, actually... if you want to play Rainbow Six, go download Black Ops, which lets you play R6 and Rogue Spear with all their expansions. Rainbow Six 3 is just not quite as good somehow - shooting doesn't feel as good, team sizes are smaller, maps just aren't as tight. But look, it's still good, alright. It's fine.
Postal 2 (2003) - yeah, it's a load of shit, but there's never really been anything else like it. Do a pacifist run if you want to have a really hilarious time.
Call of Duty (2003) (and United Offensive) - not much to say that I didn't already say for Medal of Honor. Is the WW2 setting deeply boring? Yes. Are you fighting the same guy over and over again? Yes. Does it work anyway just through sheer quality and smoothness? Yeah, I think so.
Far Cry (2004) - I fucking love Far Cry. It's superb. It's genuinely brilliant. No, it's not just an "tech demo", DO NOT CALL IT A TECH DEMO. Weapons all feel great to use, headshots are unbelievably satisfying, vehicle segments are always welcome, and you go through a whole range of locations. Play on highest difficulty if you want a laugh, the jeep section where Val's driving and you're on the gun is almost impossible to beat.
Doom 3 (2004) - yeah yeah, it's Doom 3, yeah yeah, flashlight, yeah yeah, monster closet. I don't care, I think this game's fine. BFG Edition is the one to play, since it fixes the flashlight insanity.
Gaylo 2 (2004) - I enjoyed this more than the first one overall, I think. The FMV cutscenes in the Master Chief Edition are fucking amazing.
Half-Life 2 (2004) - I'm not a big fan of this game, and I know a lot of other people here aren't. Vehicle sections are boring, combat feels utterly weak, enemy AI sucks balls, the story is badly written and highly intrusive, and the gravity gun gets old after about thirty seconds. Mentioning it just because I can't not mention it, and I do think it's worth playing today just to see what you make of it - I'd be interested to hear what someone who's never played it before would think, especially if they haven't been primed with the "oooh you're about to play one of the GREATEST GAMES OF ALL TIME" horseshit.
SWAT 4 (2005) - fucking fantastic, absolute high watermark of tactical shooters. Play on hardest difficulty or you're a pussy. Oh, you're mad because you failed the mission with a score of 94 out of the necessary 95, just because you shot a guy who was screaming "DIE PIG" and firing a bullet into your head? Well maybe you should go back to police academy you fucking rookie. Just because someone has shot one of your eyeballs out doesn't mean it's acceptable to shoot back. Go learn the rules of engagement, and bring the paintball gun next time.
F.E.A.R. (2005) - story's a load of shit but wow, what a fun game. Just radiates coolness. The combat is extraordinary, what else do you need
Mirror's Edge (2008) - okay, go ahead and tell me it's not an FPS. Look, I don't know if you've noticed, but the last entry on this list was 2005. There's fucking nothing in the late 2000s, it's a wasteland. Just let me have Mirror's Edge. I love this game.