Je prends le format qui est le plus intéressant selon l'image: les photos c'est généralement JPG, mais dans beaucoup d'autres cas le GIF (en 32/16/8 voire même 4 couleurs) est plus compact. De plus, dès que tu as du texte ou un truc assez précis (des traits bien nets), on ne peut pas plus trop utiliser le JPG à cause du 'lossy'.
Et, pour les images en couleurs indexées qui ont pas mal d'à-plats, PNG est bien meilleur que GIF.
Moi j'utilise Photoshop CS (la première version de Photoshop à faire des PNG suffisamment réduits en taille), mais il y a des utilitaires genre PngOptimizer qui font des choses très compactes.
Bon, mais si les couleurs sont pas bonnes...