Playing animated gifs is pretty easy, it was done in ferretboys funbrew with PAlib. Would certainly add a little something to it.
Gif's are extremely VRAM-monging, they're not recommended to say the least in PALib nowadays. Use Gif2Frames, a tool attached to the PALib toolchain and create sprite strips instead or you're in for some nasty lags.