As imagens em .GIF caracterizam-se por serem imagens com poucas cores. Quanto mais cores tiver mais peso terão e logo perderam sempre qualidade.
Só mesmo diminuindo o número de cores (se possível), tornar a imagem mais simples é que resolve o problema.