Actually it might be preferable to always use the polyfill if you want to do something like the Apple thing where you can scrub around the video. Still doesn't have I-Frames to do frame-skip during fast movements though.
Based on my hazy understanding of the animated GIF file format, I believe that what I ended up with is very similar to animated GIFs, from a high level at least (i.e., a collection of frames, each of which containing multiple rectangles where the frame differs from the previous one). I have no idea why the animated gif encoders I tried did such a poor job size wise, it looked as if none of them even tried to find the minimal set of changes from one frame to another. I didn't spend too long looking, as 8-bit color was always going to be a show stopper.
GIFs standard is awesome, it is that most of the software does them wrong. To recap:
You can update multiple rectangles each with 0ms delay. Issue is that most browsers don't like dealing with 0ms updates, and will consider rectangle update a frame update. Some browsers will silently increase delays. 
You can pause once all necessary rectangles for frame have been updated. 
You can have full colour image provided that it is built from multiple rectangle updates, where each rectangle contains its own colour map. 
Indeed, it is very strange that an animated GIF would be so ineffective in this case. The image does not seem to have too many colors and the animated changes are minimal. Have you tried an encoder that attempts to use at least the basic GIF optimization techniques?