Cave Wars for the PC. Might actually be an Avalon Hill PC game before AH was bought by WotC. Think Civ with a strealmlined tech tree, and no economics/politics, with 3D movement, because the world was all in a cave. You could build drills that could connect upper and lower levels.
I'm also a big fan of Crimson Skies. If FASA/Wizkids or whatever they call themselves these days would ever get their act together, it'd be nice to see a 360 sequel someday.
We played the crap out of the first Star Control in college. Back then, we'd have two people sharing a keyboard for the controls on a tiny PC CRT screen.
Metal Arms was a great little platform shooter for the Xbox. It could have been even awesomer if hte mutliplayer aspect had been done better.