Devido à forma como os GIFs funcionam, quanto mais complicada a paleta, o gif resultante se torna maior rapidamente.
Eu usaria o GIMP para otimizar o GIF resultante de # 2 - não 100% de certeza de como funciona, mas acho que basicamente exclui informações duplicadas de um quadro para outro.