I don't play too many games anymore, so I have to re-route my nerd obsessiveness into game soundtracks nowadays.
Seconding Cave Story and every Genesis/Megadrive Sonic game (except maybe Spinball).
3D Blast often gets overlooked, and when people do pay attention to its music, it's usually the Saturn version. Which admittedly does have great music, but the Genesis version has some fantastic music too!
Rare had a stellar string of soundtracks (alliteration!) on the N64 going for a while; Blast Corps, Diddy Kong Racing, and Banjo-Kazooie all have superb music. While we're on the 64, Tetrisphere/The New Tetris and Mischief Makers both deserve mentions for being unique (and in the case of the Tetris games, the music is
absolutely kickass and some of the best on the N64, ever). Neil Voss is a minor deity.
Parappa the Rapper, Um Jammer Lammy, and Vib Ribbon for PS1 all have wonderful soundtracks.
Jet Set Radio deserves a mention. Anyone who's played it will know why.
On the PC, The Neverhood has one of the most uniquely charming soundtracks I've ever heard for anything, courtesy of Terry Scott Taylor. I cannot recommend tracking this game down enough, if only for the music. Here's the main theme:
http://youtube.com/watch?v=DXQ2lvgpHiE
But the best game soundtrack of all time? Earthbound. No question.