If you are using the GD library to resize images automatically, and are making use of the GD resize functions, try resampling the image instead. i.e. if you are using PHP, use imagecopyresampled() instead of imagecopyresized(). in Ruby; copyResampled() instead of copyResized().
This is recommended if one desires a better quality image when resizing images with GD, and has been successful for that purpose in my experience.