Weird - was just thinking about this very topic the other day and started reminiscing...
Descent was awesome as was Wolfenstein 3D, Doom, Duke Nukem 3D, Sim City (I also enjoyed Sim Ant for awhile in there), Warcraft I & II...what else?
Dominator mentioned Indiana Jones and the Fate of Atlantis (awesome adventure game!)...
Starcraft, Diablo I & II, Earthsiege II, Starsiege (was never into Tribes)...
mustanger mentioned Chuck Yeager's Air Combat (LOVED that game; I still have fond memories of trying to take a P-51 up against MiGs in a custom scenario)...
Elder Scrolls I: Arena was great...
A couple other newer ones that didn't make the list that I enjoyed:
Deadly Tide (gameplay may have been lacking, but the story was a good one, the action was fast-paced, and the music - a big thing for me - was phenomenal...still hated the ending, but oh well)
Drakan: Order of the Flame (a cute chick with a sword and a fire-breathing dragon? Is there anything more you could want out of life?!)
Tomb Raider III (didn't play any of the others)
And here's one that doesn't quite fit the criteria because I think it was released in 2000, but was still great nonetheless for all us closet-case dogfighters:
Crimson Skies
....yeah...life was good...