hay maneras de optimizar las imagene por ejmplo con Photoshop (al menos CS2 ) tiene una opcion que dice "Optimizar para Web" y te crea un archivo gif ligero y de buena calidad (con algunas excepciones en fondo blanco y sombra tendrias que probarlo) pero los degradados si lo respeta
Supongo que hay mas programas esta tan solo es una opcion, incluso fireworks tal vez tenga alguna opcion por el estilo