"Optimized" in this sense meant that animated gifs can have a frame reference only three pixels of the original image. So an image of 300K with only small movement (think cinemagraphs) wouldn't be much larger.

This is a given for movie formats, but at the time the animated GIF came up it was revolutionary. I think the proper phrase should be "animated GIFs can be pretty optimized, taking into account how inefficient the algorithm is, when compared with other animation algorithms of the time".

I also think there's an interpretation that applies here: When you see an animated gif, even if it's a frame that changes three pixels and nothing else, internally the renderer may be expanding it into a full movie (that is, uncompressing each resulting "frame"). This usually makes GIFs (regardless of how large or small the GIF actually is) take much more memory than common sense would tell you.