It's not quite that stark. You can have the non changing background solely in the first frame, and have subsequent frames (smaller frames even, placed at offsets) composed solely of "sprite like" things that overlay. And there are tools like imagemagick​ that can optimize existing animated gifs in that way. It is crude, but it's more than just a plain sequence of unrelated full size frames .

> Animated images aren't that smart, they're just a bunch of images, so you're storing every single frame.

GIF89a has a sort of limited delta encoding via the "do not dispose" option. If you write a frame with "do not dispose" and then write a frame with some transparent pixels, the transparent pixels will retain the colors from the previous frame.

It's rather primitive but it's better than nothing.

Disagreed, BPG (better portable graphics) is based on H265, but aimed at animated/nonanimated pictures. From my tests it runs really well.