Got some free time and decided to skim through the GIF Specification. For a layman (i.e. me) it's pretty dense. That said, I think I've found what makes the optimization possible.
For context, under the general description section it states:
The Graphics Interchange Format is defined in terms of blocks and sub-blocks which contain relevant parameters and data used in the reproduction of a graphic.
It goes on to describe the different types of blocks and sub-blocks. From what I can tell, "Graphic Control Extension" blocks are the ones that make animation possible and essentially act as frames. They allow for a "Delay Time" value, and also allow for a "Transparency Index", which is described as:
The Transparency Index is such that when encountered, the corresponding pixel of the display device is not modified and processing goes on to the next pixel. The index is present if and only if the Transparency Flag is set to 1.
Interesting! So in the GIF format, tranparency means "don't draw anything in this space".
The final piece of the puzzle is the Graphic Control Extension's "Disposal Method":
Disposal Method - Indicates the way in which the graphic is to be treated after being displayed.
Values:
- 0 - No disposal specified. The decoder is not required to take any action.
- 1 - Do not dispose. The graphic is to be left in place.
- 2 - Restore to background color. The area used by the graphic must be restored to the background color.
- 3 - Restore to previous. The decoder is required to restore the area overwritten by the graphic with what was there prior to rendering the graphic.
- 4-7 - To be defined.
If the previous frame isn't disposed of, transparent pixels will allow that frame to show through. But if the previous frame is replaced with the background color...

As you can see, only the pixels that have changed since the last frame are updated, and the rest have been left unaltered (transparent). That's a lot less information to store.
When transparency is disabled, every frame has to be drawn in its entirety. So that's why enabling transparency in an animated gif saves space.
If you're reading this, you might also want to check out this article, which goes over how the gif disposal method works in plain English. It does it in the context of a gif editing program called GIFBuilder but it's still good info!
Finally, if anyone else has more insight into this please jump in.