Use o gifsicle (disponível para Mac OS X e Windows ).
gifsicle -i anim.gif -O3 --colors 256 -o anim-opt.gif
Isso otimizará e reduzirá para 256 cores, se a animação usar mais cores (a imagem do exemplo).
Você pode reduzir o tamanho reduzindo o número de cores:
Combaseem