Yo creo que las imagenes deben estar en gif q seguro te ocupan menos. Un programa con el que puedes optimizar cada frame del gif animado es el macromedia fireworks que te abre el gif en capas o frames( una por cada "movimiento o grafico",no se si me explico). Desde aqui lo exportas y ahi tienes varias opciones para optimizar cada frame por separado. Puedes suprimir colores q no se usan y demas cosas. Luego lo exportas como gif animado y listo. Lo suyo es ir probando diferentes configuraciones. el mismo programa te dice cuanto te va a ocupar antes de exportarlo.
Prueba la trial del programa:
trial fireworks
Aunque te vas atener que hacer una ID de macromedia para poder descargar trials (es gratis, el hacerte el ID digo
)
saludos