Да уж, в адобе с размерами не стесняются:(
Есть такие простые правила для уменьшения размеров...

-уменьшить размер картинки;
-уменьшить число цветов в палитре;
-в меню фотошопа использовать "Export for Web";

Если это не анимация, хорошо помогает "Advanced JPEG Compressor", для анимированных gif' ok даже не знаю... в некоторых графических редакторах есть такая опция, "Save optimized" или что-то подобное.

А вообще, стоит ли мучиться с GIF - анимацией? На Flash можно сделать гораздо больше.