GIF is not very CPU-intensive, but I definitely remember systems slow enough that JPEGs loaded at visible speed over a couple of seconds. I also had a Libretto 30 that could play MP3s, but only with the Fraunhofer decoder and not the Winamp one which couldn't quite keep up with realtime.
I remember this myth, saying that the first moon landing required as much computing power (command central, ship etc.) as rendering a GIF. No mention about the resolution, frame speed and so on, though. Hence I think it's a myth. On the other hand you could probably tune those parameters enough to actually make it a true statement ...