Unreal Tournament in 1999 was such a great game back then with its outstanding graphics engine during its time. It's main competitor was Quake 3 Arena which didn't look quite as good but still addictive.
The big releases in 2004 that remain in my mind are:
1. Unreal Tournament 2004 (which still played heavily to this day with the massive amounts of mods for it).
2. Battlefield Vietnam (this has pretty much been overshadowed by BF2 and BF2142 now).
And after that you have to start looking at the all time greats like:
1. Starcraft (1998)
2. Master of Magic (1995?)
3. X-Com (1995?)
4. Civilizations 2 (1996)
5. Doom & Heretic (playing those game multiplayer on an old Novell IPX network was 'da bomb' back in the day.... In the case of Heretic...name one other FPS where you can turn a guy into a chicken for the fun of it....)
Starcraft/Brood War (I've played this more than anything, thousands of hours prob)
Command & Conquer (the whole series is the bomb, i haven't played generals though, tiberian universe my personnal fav, but the attack dogs in RA(i think it was RA) were so much fun)
Homeworld/Cataclysm (Great story, gfx, controls were fluid)
Diablo 1 & 2 & LoD (fun stuff)
Warcraft II (fun stuff)
X-COM (we played this at the school library, fun!)
System Shock 2 (Monkey with brains sticking out still freaks me out!)
So many other games..
Today's games don't hold a candle to the great titles of yesteryear, the "young" (cough, i'm 23.. old i guess) generation don't know the greats that came before the clone cr4p that comes out today by EA and M$.
PS. Not considering my old commodore a PC, those had some great games, then my parents got me a nes...