Windows: RIOT, or Radical Image Optimization Tool, compresses your images as much as possible without turning them into a horribly pixelated mess. The app gives you a side-by-side view of the original and the compressed version so you can see how the final image will appear.
RIOT allows you to configure exactly how compressed the final image will be. Naturally you'll lose some image quality when you compress, but the RIOT pays close attention to how much is lost and starts with unnecessary data first. You can always dial the compression back without altering the original image. Also, you can see what the final file-size will be above the preview of the compressed version.
RIOT is free, and Windows only. If you're already using The GIMP, IfranView, XNView or another plug-in capable image editor, you can download the RIOT plug-in for those applications as well.