La otra alternativa es que NO generes GIF sino SWF (animacines Flash) ..
Para eso PHP dispone de su extensión MING
www.php.net/ming
Pero .. NO es para nada normal verla instalada en servidores .. ni de pago ni mucho menos gratuitos ...
Un ejemplo sería este:
http://sourceforge.net/projects/jpg2swf-thumb/
usa GD y MING para generar desde unas imagenes "bitmap" una animación o "película" en SWF (ejemplos parecidos y más simples tienes en la documentación de PHP.net sobre MING)
Un saludo,