Everyone else has already said much of my choices, but here's some other games I remember:
SkyRoads
I'm still addicted to this game.

It's kind of hard to explain, basically you're in a craft jumping around a platform track in space. You have to reach the end of the track before your ship runs out of fuel. Different color track pieces have different effects, such as refueling your craft, speeding you up, or killing you instantly. Music is pretty kickin'.
Descent
I think this was one of the first true 3D shooters out there at the time. I don't know what else to say, pretty fun.
Duke Nukem
The first Duke game, side-scroller. The level design is pretty damn good, fun and addictive. And come on, PC speaker sounds!
Elder Scrolls: Arena
If you like Daggerfall, chances are you'll like Arena. Same kind of deal.
Lemmings
It's Lemmings, little green haired creatures that want nothing more than to hurl themselves off ledges to their certain death. But we can't have that can we? Puzzle game, if you don't already know.
Terminal Velocity
Another 3D shooter, kind of like Descent, but you get to fly around in more open areas. Get's kind of annoying and challenging at times, but I remember playing it as a kid so it goes on the list.
Wolfenstein 3D
The first-person shooter. It basically started it all. Even though it gave me terrible motion sickness at times (and I rarely get motion sickness) I still love it. If you haven't tried it, try it.
Spear of Destiny
Something of a sequel to Wolfenstein 3D. If you couldn't get enough of Wolf3D, then here you go.
(Edited to not piss BN off with lists.)