Yarg. I hate it when I hit the close button after only a preview.
Anyway, here was the list I had thought of:
Tie-Fighter, Heroes of Might and Magic 2 (never played the first, but my GF is still playing this one), Descent:FreeSpace 2, Dark Forces. Oh, right. I have to agree with the call for StarCraft. I really enjoyed that one very much.
I'm also trying to find a game to capture my attention right now. I've been trying to play Diablo 2, but it's just not enough. I'm not quite sure what I'm seeking in a game, though.
And for the Lemmings fan, I think I had found a version of it online in a Java game. It had sound effects and music that kept the feel of the original. I'm not sure if it is still out there.