I cannot see your images so I am not exactly sure what is happening.
I use photoshop to handle my compression (save for web and devices, compression varies based on image but i try to keep all main images under 200k). I also don’t let magento handle the conversion between main, small, and thumbnail, only small to thumbnail. I upload images via csv, not the magento interface (a whole other thread) and it works swimmingly (i.e. no poop in the pool).
You can also disable jpeg compression on magento’s end:
But I have yet to have to do this as my images are just fine as they are now. You can see them at: