Juste pour pinailler : si tu divises par 2 la hauteur et la largeur de l'image, tu divises bien en fait l'animation (qui est une surface, comme toute image 2D) par 4, cqfd ;-)
Tu peux aussi optimiser en diminuant le nombre d'images, sachant qu'on peut varier la durée d'affichage de chaque image… mais c'est sûr que tu ne gagnera pas tant que ça de poids, enfin ça dépend de la complexité des images.
Il y a l'optimisation à mort de la palette de couleurs, on peut remplacer une couleur par une autre proche pour réduire la palette, ça peut se peaufiner aux petits oignons, là aussi on peut gagner pas mal.
Mais comme dit Nico, le format gif n'est vraiment pas fait pour les animations longues et complexes. Pour cela, il y a la vidéo ou les animations type Flash, qui auront l'avantage de pouvoir se streamer, donc même lourdes elles se lisent mieux car elles démarrent plus rapidement…