Edit: Actually I just changed the desktop settings to 16 bit color, since the image data in the game is 16 bpp, and it's a little better. It now looks like this:
But I don't want people to have to change their desktop settings just to play the game...