I'll go the same route as ZTC and go by genre:
Adventure
The Broken Sword series (Might be a little hard to track down in the USofA, but if you can, do so)
Grim Fandango (If you can get it to run)
The Monkey Island series (Use DosBox for the first two, the later two should work fine on WinXP)
Sam & Max (The original Lucasarts one and the newer Telltale ones - all rock)
The Longest Journey and Dreamfall (Awesome and underrated series)
FPS
Bioshock (which you're already interested in, so consider this confirmation)
Deus Ex (Hard to place in any one genre, but it's a cracker of a game)
Doom 3 and Resurrection of Evil (well, you did mention Quake...)
Painkiller (see here for why)
Unreal Tournament series (I prefer the simplicity of the first one, but the sequels are also great fun, and actually come with challenging bots)
Platformer
Beyond Good and Evil (it's finally getting a sequel! Yay!)
Grand Theft Auto series (So much better on the PC it's 'criminal'. ...sorry.)
Max Payne 1 and 2 (Bullet Time for teh win)
Prince of Persia: Sands of Time trilogy (Again, Yahtzee explains it far better then I could)
Tomb Raider Legend and Anniversary (Both are surprisingly good fun)
RPG
Anachronox (Hard to track down, but well worth the effort. Ion Storm's best game, and I will hear no arguments to the otherwise)
Baldur's Gate series (I really don't need to justify this, do I?)
Neverwinter Nights (For all you D&D loving fools who can't do without all 3 of the D's)
The Elder Scrolls series (Morrowind and Oblivion, which are both so big it's possible to actually get lost)
Star Wars: Knights of the Old Republic series (Two of the best Star Wars games ever)
RTS
Command & Conquer series (Because Westwood is the Daddy. Or the Governor. Or something. Meh, they rock. Except for Renegade. Stay well away from that misfire.)
Freedom Force series (For Freedom! A superhero RTS series that's funny and fun? For excelsior!)
Starcraft series (With the new one due out sometime next year - and it will be next year - there's never been a better time to get into this)
Warcraft series (Because. Just... because.)
There's a few games I haven't mentioned, since you already mention having them. The Half-Life series, for example. I would, however, try the first Fallout, since the new one is essentially going to be that but in 3D (and without the turn-based combat).
Since most of my list are relatively old you can download some of the adventures as cough*abandonware*cough, but the majority of them are quite cheap these days. As you can tell, I'm a bit of a retro gamer myself - modern games are all too bright. And brown. Because realism is apparently bloomin' brown. Meh.