Found what was wrong.
Disabled 8-bit palettes, left antialiasing as default, and set my driver to nvidia TNT.
Thanks for the info, I'll check the
FAQ next time -_-'
Suggestion, though lots of work:
You could probably sharpen the backgrounds of the game to keep the pixels clean. Hurts the eyes sometimes lol.