Pues instalar ImageMagick?
O en dado caso vas a tener que "romper" el gif en sus frames y redimensionar cada frame, ten en cuenta que es un trabajo muy pesado para PHP, pero hay clases en PHPClasses.org que separan un GIF en frames, luego redimensionas cada frame por separado y vuelves a "juntar" el gif animado.
Saludos