I must say that I disagree here, Jason.
Maybe in past versions of Photoshop the application wasn't very good with image optimization, but with any of the recent CSX releases (I'm running 5 or 5.5, but same goes for 3 and 4 at least) it does a wonderful job. The key is in using the "Save for Web & Devices" feature rather than "Save As."
If I understood our recent conversation on the subject correctly, Paint Shop Pro doesn't support the latest and greatest of JPG optimization, either. (or, at least the version you're using?) As you may recall, I took an image you saved from Paint Shop Pro at 200KB down to under 100KB with reasonable quality in Photoshop.
I believe Photoshop does an excellent job with PNG's this way as well because I have run the results through PNGCrush and it returns the same file size, (sometimes a few bits smaller, or larger) even using brute mode.
I've spent a good deal of time lately playing with and researching image optimization for the web and Photoshop has established itself with me as a trusted and invaluable tool during that process.
You said in your original post that you are uploading these to a gallery after you save the images, right? Once uploaded, the full 1200x800 size looks fine, but the thumbnails have low quality, correct?
If so, then what gallery are you uploading these to? It sounds like your problem may be there, in the creation of the thumbnails.
You may want to consider bringing the full size images down a bit smaller from 1200x800 and dropping the quality to 50-60%, too. (This won't resolve thumbnail quality issues, but is probably best practice for the web)