Se è un gif molto complessa, beh : Utilizza Photoshop. Niente di piu semplice.

Utilizzi l'opzione di salvataggio Save for Web e ti regoli tu. Puoi diminuire appena la qualità d'immagine se proprio non rientra nella misura che ti serve!