are you changing the quality settings in the optimization menu, or when you go to "save for web" or "save as" normally a jpg saved at 60% quality has a pretty low quality loss, go below and youll see the difference
I use Photoshop's "Save for web" option and play with image type, quality and number of colors. Sometimes GIFs work better, sometimes JPGs work better and every now and then PNGs work better (but not often). It is all a matter of trial and error for each graphic.