Today I stumbled upon this:
Canvas Cycle: True 8-bit Color Cycling with HTML5 
Take some time to see it, it's awesome. And beautiful. And Art.
My first reaction was: I have to know if this guy (Mark Ferrari) was ever involved in the design of a game; Turns out I already played some games containing his work! Mark worked, with Steve Purcell, on the art for Monkey Island™, and illustrated Loom™ as well.
My question is:
Can you help me find games with art this gorgeous? I'm referring especially to 2D games which show high care in the details of backgrounds (of course foreground art is important as well).
Bonus points if the game can still be played somehow, and if it features good game mechanics and a good plot.
I recommend The Dig . Decent quest with beautiful background pixel art, which bundled with the great soundtrack really helps build the atmosphere. A lot of caverns and ocean and weird rock formations.
And it has a higher resolution than Loom :)
Available on Steam for 5$  (or 10$ bundled with a few other games, including Loom). http://en.wikipedia.org/wiki/The_Dig
Perhaps not beautiful, but I always found the Metal Slug graphics  to be an impressive demonstration of what can be done with a minimal number of pixels.
At the other end of the scale, I've always loved the minimalism of Another World . http://www.google.co.uk/images?&q=Metal+Slug
Mobygames can give you a list of all games he's been credited on.
I've always been fascinated by the beautiful graphics (and the music) in The Legend of Kyrandia .
The game does have a nice story and decent gameplay (standard adventure gameplay, but sadly with a few needlessly frustrating puzzles). You can play it using dosbox or scummvm without any trouble. http://www.mobygames.com/game/legend-of-kyrandia
I remember that there was a game already in the 24bit color time, that still came with 8bit. It was called I-War. Came out in 1998. It was a space shooter like Wing Commander if I remember correctly and looked really good. They really got everything out of 8 bit.
I remember Star Trek: Hidden Evil  had gorgeous backgrounds (and high polycounts on foreground, because all of the backgrounds were static.) http://memory-beta.wikia.com/wiki/Hidden_Evil