System Shock
Aliens vs Predator

...and Aliens vs Predator 2. :)

I'll have to also recommend FEAR. The "horror" aspects of it aren't exactly scary, but its a fun shooter that I've replayed many times in the years since. Too bad FEAR 2 went a direction I disliked.
(I often say when i got fear 1+2 on steam a few years back for $7 that I paid $10 for Fear 1, and they payed me $3 for to take a copy of Fear 2.)

And if you're going as far back as the 90's You've got to include DOOM if you haven't already played it. Great fun, and you can still find the shareware WADs floating around to try it first.

A comment on the UT2k4 recommendation... I had great fun in that game.
It, however, is a 10+ year old game that was mostly multiplayer. I'm sure there are sill servers out there.. but its not going to be as populated as it once was, and therefore maybe not as enjoyable.

'05 should be late enough to include this... don't feel like looking up the release date.
Half Life 2. Yeah yeah, everyone talks it up so much...
Its not the godsend that some people seem to think it is, but its still a fun story FPS.
(Hey, you didn't say GOG games only :P)

The "simple" stuff:

Doom (obligatory) + a bunch of good mods;
Half Life + expansions & Half Life² + episodes (stretching a bit because the episodes are past 2005) + another bunch of good mods;
Return to Castle Wolfestein;

The "2deep4u" (a.k.a. what is this RPG thingies doing in my shooter?) stuff:

Deus Ex;
System Shock & System Shock 2 with the caveat being that they can be quite hard to "get into" (worth it IMO);
Another stretch to include S.T.A.L.K.E.R. Shadow of Chernobyl (2007);

Also, if you want to kill time looking for some obscure shooters try this playlist, it's at the very least, quite entertaining to watch IMO. :)

F.E.A.R. + Expansions
Quakes 1-4
Call of Duty 1
Serious Sam First and Second Encounter
Red Faction 1-2
Battlefield 1942, Vietnam, and 2
Vietcong
Unreal 1 and 2
Unreal Tournament 1999 and 2004
Return to Castle Wolfenstein
Far Cry

That's a pretty decent representation of the genre, and some of the best in my opinion.

Edit: Can't believe I forgot Medal of Honor: Allied Assault + Expansions, Pacific Assault, and Airborne.

Star Wars : Jedi Outcast is a surprisingly fun and competent shooter until you get your lightsaber. And even then you can continue to play it as an FPS, except for most fights against force users in which you'll get your ass kicked if you don't use your lightsaber.

I'd also like to throw Unreal out there (on normal difficulty). It's possibly the best FPS I've ever played. Incredibly atmospheric with very good level design that often allow for more than one approach.

Kingpin also gets a lot of praise and I definitely did have a lot of fun with it in the beginning. Got a little stale for me though after that, or repetitive rather. Still there isn't anything else with its type of atmosphere.

FEAR Platinum
Return to Castle Wolfenstein
Clive Barker's Undying

^All of them are great shooters.

From GOG?

Serious Sam and Serious Sam: Second Encounter. You'll love them, or if you don't, well that's your problem then!

Sorry, should've said Gog yeah

- Doom
- Strife
- Quake
- Jedi Knight
- Unreal
- Clive Barker's Undying
- Return to castle Wolfenstein

Sadly there are better versions of the SS games on Steam.
TFE and TSE's Multiplayer no longer works as far as I know.
There's a fan version on Steam that combines both games and fixes the multiplayer.

doom II
jedi academy
quake 4
doom 3

A lot of people don't like it, but I really enjoyed Blood 2. It has a great atmosphere, although the later levels do feel rather lazy.

Prey
Clive Barker's Jericho

The older (GOG) versions are still good too, with the added benefit of running better on lower end PCs.

I actually prefer the old (non-HD) version of the first game as the desert doesn't have dunes like in the HD remake. The undulating dunes in the remake mean you'll have issues shooting your rockets at a robot in a horizon etc. The flat desert in the original game is better IMHO.

Plus, since he was asking for games older than 2005... The HD remakes are newer, from around 2009-2010 I think..