А встроенные средства не помогают?
Типа "Save as Web", палитру уменьшить.
Я раньше GIF Movie Gear сжимал. http://www.gamani.com/ - платный.
Потом, оказалось что gimp'ом нормально выходит, родными инструментами. Неужели в фотошопе хуже?
http://x128.ho.ua/color-quantizer.html
color quantizer
Просто охуенная утилитка!!!
Мне тут на форуме ее тоже посоветовали!
У меня то что было фотошопом сделано 10кб уменьшало до 1кб при это визально если не присматриваться ухудшения качества не возникало.
работает с GIF / PNG / JPG
вот тут есть какие-то рекомендации еще
Юзабилити под Googler ;)