Oh, people mentioning Crimson Skies. That's a great game (GOG, you working on this?) that, though obviously graphically outdated, has really stood up to the test of time. A franchise I'd like to see revived, for sure.

There are no-CD patches available, and I believe someone sorted out the compatibility issues with modern OS's and did an FHD mod as well. You know, in case you snatch up a copy on eBay.

I got lucky and got a reasonable condition big box version from eBay about five years ago for £10. Great game.

1996:
Panzer Dragoon II Zwei (SAT, 1996)
Command & Conquer: Red Alert (PC)
Saturn Bomberman (SAT)
Mole Mania (GB)
Soul Blade/Soul Edge (PS1, 1996)
Warcraft II: Beyond the Dark Portal (PC)
Front Mission: Gun Hazard (SNES)
Kirby Super Star (SNES)
Diablo (PC)
Heroes of Might and Magic II: The Succession Wars (PC)

Mario Kart 64 (N64)
Battle Garegga (ARC, 1996/SAT, 1998)
​NiGHTS Into Dreams... (SAT) & Christmas NiGHTS into Dreams... (SAT)
Soukyugurentai (ARC, 1996/SAT, 1997)
Tekken 2 (ARC, 1995/PS1, 1996)
Super Mario RPG: Legend of the Seven Stars (SNES)
Strife (PC, 1996)
Dragon Force (SAT)
Dragon Quest III: Soshite Densetsu e... (SNES)(Remake)
​Quake (PC)

PowerSlave/Exhumed (SAT)
Lords of the Realm II (PC)
Metal Slug (ARC/NG)
Street Fighter Alpha 2 (ARC/PS1/SAT)
​DoReMi Fantasy (SNES, 1996)

I tried to focus on the obscure stuff. Played them, and had a good experience.

Battle for Wesnoth
Champions of Norrath: Realms of Everquest
Downhill Domination
Fahrenheit
Oddworld: Abe's Oddysee
Oddworld: Abe's Exoddus
Robot Alchemic Drive
Shantae
Syberia
Syberia II
Sanitarium

Red faction for it's breakable environments. Tribes games were released for free here.

https://www.tribesuniverse.com/

A problem you may find is that there will be mods for those games that aren't easily found or experienced as they were in the past.

1995:
Super Mario World 2: Yoshi's Island (SNES, 1995)
Warcraft II: Tides of Darkness (PC, 1995)
Terranigma (SNES, 1995)
Ristar (MD & GG, 1995), GG ver.
Donkey Kong Country 2: Diddy's Kong Quest (SNES)
Chrono Trigger (SNES)
Micro Machines: Turbo Tournament 96 (MD)
Alien Soldier (MD)
Virtual Boy Wario Land (VB)
Lords of Thunder (PCE CD, 1993/MCD, 1995)(easier, remastered OST)

Secret of Evermore (SNES)(w/ mods)
Sylvan Tale (GG)
Hamelin no Violin Hiki (SNES, 1995)
Galactic Attack/RayForce/Layer Section/Gun Lock (ARC, 1993/SAT, 1995)
Command & Conquer (PC)
Ginga Fukei Densetsu Sapphire (TCD/PCE CD)
The Raiden Project (Raiden II) (PS1, 1995)
Darius Gaiden (ARC, 1994/SAT, 1995/PS1, 1996)
Der Langrisser (SNES)(Langrisser II port/remix)
Suikoden (PS1, 1995/SAT/PC, 1998)

Kirby's Dream Land 2 (GB)
Super Turrican 2 (SNES)
Tetris Attack (SNES)
Albion (PC)
NHL '96 (MD/PC/SNES)
Mega Man X3 (SNES, 1995/PS1/SAT, 1996/PC, 1997)
Earthworm Jim 2 (SNES/MD w/ mods, 1995/PS1/SAT/PC, 1996)
Street Fighter Alpha: Warriors' Dreams (ARC/PS1, 1995/SAT, 1996)
Lufia II: Rise of the Sinistrals (SNES)
Light Crusader (MD, 1995)

My recommendations from before 2006 without any other criteria for selection:
- Doom series up to Doom 3
- Quake 2 and 4
- Descent 1,2,3
- Descent Freespace and Freespace 2
- F.E.A.R. Platinum and its expansion packs
- Battlezone 98 Redux with The Red Oddyssey included
- Battlezone 2
- XIII the first game (and it's on giveaway now on GOG, go get it!!)
- Crysis
- Far Cry (the first game)
- Wing Commander Prophecy
- Vangers (excellent game)
- Deus Ex (not particularly a fan, but many people swear by it)
- Return to Castle Wolfenstein
- Tron 2.0

EDIT: Forgot to add:
No One Lives Forever series, sadly unavailable in fully legal form now.

There are many others which others would consider essential, but I'm yet to play them so I cannot recommend them in good faith.

1994:
Super Metroid (SNES, 1994)
Wario Land: Super Mario Land 3 (GB)
Langrisser II (MD, 1994)
Panorama Cotton (MD)
Lunar: Eternal Blue (MCD)
Sonic the Hedgehog 3 & Knuckles (MD), Sonic 3, Sonic & Knuckles
Contra: Hard Corps (MD)(JP ver.)
Donkey Kong (GB, 1994)
Donkey Kong Country (SNES)
X-COM: UFO Defense/UFO: Enemy Unknown (PC)

Puyo Puyo 2 (MD, 1994/SNES, 1995)
Mega Man X2 (SNES)
Darius Gaiden (ARC, 1994/SAT, 1995)
Castlevania: Bloodlines (MD)
RayForce/Galactic Attack (ARC, 1994/SAT, 1995)
Monster World IV (MD)
Wild Guns (SNES)
Yu Yu Hakusho: Makyo Toitsusen (MD)
Dynamite Headdy (MD)
Alien vs. Predator (ARC)

Final Fantasy VI (SNES, 1994)
Micro Machines 2: Turbo Tournament (MD/PC)
Mega Turrican (MD)
Elevator Action Returns (ARC, 1994/SAT, 1997)
Streets of Rage 3/Bare Knuckle 3 (MD, JP ver.)
Super Street Fighter II (SNES/MD)
Snatcher (MCD, 1994)
Demon's Crest (SNES)
Crusader of Centy/Soleil (MD)
Sega Rally Championship (ARC)

1993:
The Legend of Zelda: Link's Awakening (GB, 1993)
Super Mario All-Stars (SNES)(SMB1-3 & SMB2 JP, Remaster w/ added save feature)
Rocket Knight Adventures (MD)
Power Strike II (SMS)
Shining Force II (MD)
Bomberman '94/Mega Bomberman (PCE, 1993/MD, 1994)
SimCity 2000 (PC)
Shinobi III: Return of the Ninja Master (MD)
Rock n' Roll Racing (SNES, 1993/MD, 1994)(w/ mods on MD)
Battle Mania Daiginjou (MD)

DuckTales 2 (NES/GB)
Gunstar Heroes (MD)
Castlevania: Rondo of Blood (PCE CD)
Star Fox (SNES)(emulated)
Batsugun (ARC, 1993/SAT, 1996)
Power Strike II/GG Aleste II: Lance Bird (GG, 1993)(different)
Raiden II (ARC, 1993/PS1, 1995)
Phantasy Star IV: The End of the Millennium (MD)
Cannon Fodder (AMI/PC, 1993/MD/SNES, 1994)
Mystic Warriors (ARC)

Mega Man X (SNES)
Keio Flying Squadron (MCD)
Cadillacs and Dinosaurs (ARC)
Lords of Thunder (PCE CD, 1993/MCD, 1995)
Ganbare Goemon 2: Kiteretsu Shogun Magginesu (SNES)
Android Assault: The Revenge of Bari-Arm (MCD)
​Maniac Mansion: Day of the Tentacle (PC)
Goof Troop (SNES)
Doom (PC)
Daytona USA (ARC)

1992:
Sonic the Hedgehog 2 (MD, 1992)
Thunder Force IV (MD, 1992/SAT, 1996)
Landstalker: The Treasures of King Nole (MD, 1992)
Pocky & Rocky (SNES, 1992)
Soldier Blade (PCE, 1992)
Super Fantasy Zone (MD, 1992)
Twinkle Tale (MD)
Super Aleste (SNES)
Ultima VII: The Black Gate (PC) & Ultima VII: Forge of Virtue (PC)
R.C. Pro-Am II (NES)

Ninja Gaiden (SMS, 1992)(different)
Streets of Rage 2 (MD)
Flashback (AMI, 1992/PC/MD, 1993/MCD, 1994)
Super Mario Land 2: 6 Golden Coins (GB, 1992)
Gargoyle's Quest II: The Demon Darkness (NES, 1992/GB, )
Fire 'n Ice/Solomon's Key 2 (NES, 1992)
Bomberman '93 (PCE, 1992)
Final Fantasy V (SNES)
Alisia Dragoon (MD, 1992)
​TMNT IV/Teenage Mutant Ninja Turtles IV: Turtles in Time (ARC, 1991/SNES, 1992)

Teenage Mutant Ninja Turtles: The Hyperstone Heist (MD, 1992)
Contra III: The Alien Wars (SNES)
Air Zonk (PCE)
Bucky O'Hare (NES, 1992)
The Incredible Machine (PC, 1992)
Bionic Commando (GB, 1992)
Mega Man 5 (NES, 1992)
Gate of Thunder (PCE CD)
Kirby's Dream Land (GB)
Chikyuu Kaihou Gun ZAS (GB, 1992)

Edit: Forgot Land of Illusion (SMS/GG) for 1993

Heroes Of Might and Magic 3 - Best game ever!
Diablo 2
Star Wars Battlefront II (Classic, 2005)
Far Cry

There is loads more but if you were to play one game, it should be Heroes Of Might and magic 3.