Your graphics are actually gorgeous, and they're perfectly fit for (real, not shy 800x600) hi-res. Maybe you should consider doubling or tripling up the resolution of everything. It's not as a huge task as it sounds : If you apply a filter like Mame2x, then it will still look perfectly crisp, and you could bulk-do it: I think Imagemagick does it, so you can even do it as a batch. then the game files would be rather large, but I think your game is worth it.