EDIT:
It kind of looks like somebody has already done the work and made a whole library for animated GIFs for the Teensy:
But weirdly, this library only works with GIFs up to 32x32 pixels. And it looks sort of bulky at first glance.
Shouldn't there be a leaner way to decode GIFs and display them on a TFT, even bigger ones than 32x32?
Maybe the approach to write my own GIF decoder isn't so silly after all.