2003
AquaNox
Beyond Good & Evil
Blitzkrieg
Broken Sword: The Sleeping Dragon
Call of Duty
Combat Mission 3: Afrika Korps
Command & Conquer: Generals
Crimson Skies: High Road to Revenge
Deus Ex: Invisible War
Devil May Cry 2
Donkey Kong Country
Dynasty Warriors 4
Eve Online
Freelancer
Ghost Master
Gothic II: Night of the Raven
Hidden & Dangerous 2
IL-2 Sturmovik: Forgotten Battles
Impossible Creatures
In Memoriam
Legacy of Kain: Defiance
The Legend of Zelda: The Wind Waker
Lineage II
Lock On
Manhunt
Max Payne 2
Mortal Kombat: Deadly Alliance
Need for Speed: Underground
Neighbours from Hell
Pokémon Ruby and Sapphire
Prince of Persia: The Sands of Time
Pure Pinball
Railroad Tycoon 3
Tom Clancy's Rainbow Six 3: Raven Shield
Rayman 3: Hoodlum Havoc
Restaurant Empire
Rise of Nations
Samorost
Second Life
Shin Megami Tensei III: Nocturne
Silent Hill 3
SimCity 4
Soulcalibur II
Space Colony
SpellForce: The Order of Dawn
Tomb Raider: The Angel of Darkness
TrackMania
Tron 2.0
Tropico 2: Pirate Cove
UFO: Aftermath
Unreal II: The Awakening
Vietcong
Warcraft III: The Frozen Throne
Wolfenstein: Enemy Territory
World War II: Frontline Command
XIII
Ys VI: The Ark of Napishtim

2004
Beyond Divinity
BloodRayne 2
Castle Strike
Cave Story
The Chronicles of Riddick: Escape from Butcher Bay
Codename: Panzers
Doom 3
EverQuest II
Fable
Far Cry
FlatOut
Forgotten Realms: Demon Stone
Grand Theft Auto: San Andreas
Half-Life 2
Hitman: Contracts
Jets'n'Guns
Katamari Damacy
Killzone
The Legend of Heroes: Trails in the Sky
The Lord of the Rings: The Battle for Middle-earth
Mashed
Onimusha 3: Demon Siege
Painkiller
Perimeter
Prince of Persia: Warrior Within
Richard Burns Rally
Sacred
Scrapland
Sid Meier's Pirates!
Silent Hill 4
Sims 2
Tom Clancy's Splinter Cell: Pandora Tomorrow
Sudeki
The Suffering
Syberia II
Taiko: Drum Master
Tekken 5
Thief
Tribes: Vengeance
Unreal Tournament 2004
Vampire: The Masquerade – Bloodlines
Warhammer 40,000: Dawn of War
World of Warcraft
Worms Forts: Under Siege
Yetisports

Some of the Interplay's classics (not RPG) that don't get mentioned enough:

Giants: Citizen Kabuto
Sacrifice
MDK

Deus Ex (1) and System Shock 2 are among my favorite games (all time). They've gotten a genre name: Immersive Sims (I don't know when somebody came up with that... 10 years ago or so?) It's a genre that consists of very few games though.
I consider Thief a different type of game; Stealth... or sneaking simulator :-P There's just less interaction with the environment.

Note: I consider them 'immersive' because of the very open gameplay and interaction combined with the narrative elements - not because they're played from a first person perspective.

Illbleed, SoulBlazer, Folksoul, Torico/Lunacy, Shadow Hearts 1 and 2, Final Fantasy 6, Dragon Force, Magic Knight Rayearth, Sonic Adventure, Skies Of Arcadia, Dark Savior, Nights!, PDS, Cursed Mountain, The Bouncer, Killer 7, PN 03 and I'll think of more later. Oh "Arx Fatalis".

Most definitely

- Alpha Centauri,
- HomeWorld ( though the remastered one )
- Command and Conquer Tiberium Sun

1999:
Unreal Tournament (PC)
Heroes of Might and Magic III (PC)
Age of Empires II: The Age of Kings (PC)
Tom Clancy's Rainbow Six: Rogue Spear (PC)
Gran Turismo 2 (PS1)
SoulCalibur (DC, 1999)
Baldur's Gate: Tales of the Sword Coast (PC)(Expansion)
System Shock 2 (PC)
Dungeon Keeper 2 (PC)
Homeworld (PC)

Jagged Alliance 2 (PC)
Bangai-O (DC, 1999)
ChuChu Rocket! (DC)
Metal Slug X (NG/ARC)
Command & Conquer: Tiberian Sun (PC)
Tony Hawk's Pro Skater (PS1)
Starsiege (PC)
Spyro 2: Ripto's Rage! (PS1)
​Ape Escape (PS1)
Aliens versus Predator (PC)

Journey to silius (NES)

1998:
Starcraft (PC, 1998)
Fallout 2 (PC)
Baldur's Gate (PC)
Starsiege: Tribes (PC)
Starcraft: Brood War (PC)(Expansion)
F-Zero X (N64)
The Legend of Zelda: Link's Awakening DX (GBC)(Remaster w/ some additional content)
G Darius (ARC, 1997/PS1, 1998)
Dungeon Keeper Gold Edition (PC)(Includes the Deeper Dungeons Expansion & its improved enemy AI, 3D acceleration for the gfx and a level editor)
Panzer Dragoon Saga (SAT)

Tekken 3 (PS1, 1998)
Radiant Silvergun (ARC/SAT, 1998)(added story mode on SAT)
Battle Garegga (ARC, 1996/SAT, 1998)
​Populous: The Beginning (PC)
Suikoden II (PS1)
​Shining Force III Scenario 2: Nerawareta Miko (SAT) & Shining Force III Scenario 3: Hyouheki no Jashinguu (SAT)
The Legend of Zelda: Ocarina of Time (N64)
Resident Evil 2 (PS1) & Resident Evil 2: Dual Shock Edition (PS1)
Jazz Jackrabbit 2 (PC)
Metal Gear Solid (PS1)

Real-Time Strategy
Rise of Nations
Age of Mythology

RPG
Wizardry 8
Star Wars: Knights of the Old Republic
Geneforge

Point-and Click Adventure
Syberia
Full Throttle


Platformer
Jazz Jackrabbit
Earthworm Jim
Rayman 2

Fighting
Guilty Gear X2 #Reload

"This is Freeport 9 to heavy fighter patrol - you've come in range of our scanners. Please submit your id and destination."

I'm still having fun with it (it being Freelancer) to this day. Highly recommended.

I'd start with some of the classics that had a huge impact on gaming, like Doom/Quake, Ultima Underworld (released 1992), System Shock, Baldur's Gate (revived the withering RPG genre), Fallout and others.

For many there are enhanced versions/source ports available - you can try playing them "the way they were" for shits and giggles, but frankly, modern ports make things less painful - and the true experience can only be had on a blurry CRT anyway. ;-)

I'm going to cheat by mentioning Neverwinter Nights 2, which hails from late 2006 (cheat #1). The base campaign is decent but hardly mind-blowing - it's better if you're at least somewhat familiar with the Forgotten Realms setting, but even then it's fun rather than outright impressive - but it follows on to Mask of the Betrayer (2007, cheat #2) which is my favourite RPG experience right after Planescape: Torment.

1997:
Final Fantasy VII (PS1, 1997)
Fallout (PC)
Star Fox 64 (N64)
Gran Turismo (PS1)
Dungeon Keeper (PC)
Quake II (PC)
Mega Man X4 (SAT/PS1, 1997/PC, 1998)
Castlevania: Symphony of the Night (PS1)
Age of Empires (PC)(w/ mods)
Shining Force III (SAT)

Tekken 3 (ARC, 1997)
​Alundra (PS1)(w/ mods)
Soukyugurentai (ARC, 1996/SAT, 1997)
​Star Wars Jedi Knight: Dark Forces II (PC)
Klonoa: Door to Phantomile (PS1)
Need for Speed II SE (PC)
Oddworld: Abe's Oddysee (PS1/PC)
Super Bomberman 5 (SNES)
Mega Man 8 (PS1, 1996/SAT, 1997)
Bulk Slash (SAT, 1997)

Einhänder (PS1)
Mega Man Legends (PS1)
Mystical Ninja starring Goemon (N64)
Ganpuru: Gunman's Proof/Gunple (SNES)
Theme Hospital (PC)

Some of these have probably been covered, but I'll try to avoid the obvious ones like Doom etc (not that there won't be some obvious ones below!)

Racing Games:
- Any of the Geoff Crammond F1GP series (they're all excellent, if you can find them for sale)
- Grand Prix Legends (Hard as nails though)
- TOCA Race Driver 2/3


Strategy
- SimCity Classic, 2000, 3000 or 4 (personal favourites are 2000 and 4)
- Age of Empires Series
- Command and Conquer up to Red Alert 2
- Civilization II or IV. Give III a miss. Civ 1 might be too old to be fun for you.


Puzzle
- The Incredible Machine
- Sheep (I enjoyed it, but mixed reviews)
- Lemmings


Adventure
- Pick some classic LucasArts games
- Discworld I - Noire (enjoying fantasy/the Discworld would help)


Action Sims
- Crimson Skies
- Star Lancer
- Freelancer
- Secret Weapons over Normandy

Try Syberia and several other classic point and click adventures. Careful they can be addictive, the meetings are not helping.