no one uses 800x600 anymore.. its not default any longer so there is no need to comform to those rules anymore..
Hi, my name's no one.

I figure 1024x768 users will still be able to see all the content, and so will the people using 800x600. Complaining about wasted space is their issue.

Oh. oh. oh.

Answer to the icon trouble:

Make actual thumbnails. Don't just set the image size. Actually resize them. It'll help get rid of the roughness (artifact of pixel resizing) and they'll be a ton smaller inherently.