So, it turns out the ESP8266-01 (at least the one I have) supports 1MB of storage. I had been butting up against the 512kB I thought I had, and it turns out I needn't worry.

Running this command:

ESP.getFlashChipSizeByChipId()

This means I can probably incorporate Over-the-air updates, which will be handy. I still need to keep the image under 512kB (OTA needs the space to upload the new image).

w00t!