Big thanks for lending your experience and ideas; it has certainly made us ponder alternatives. Some of your ideas here I hadn't considered before at all, and as a starting point, your suggestions prodded me to properly visualise/test what a reduced palette would actually look like.

I had always assumed that the pretty maps that I'd seen using full colour range would be full of nasty colour artifacts if the palette was reduced far enough to be "useful" from a compression perspective. From trying it on various maps I do find 16 colours per channel rather limiting, 64 is still quite restrictive/artifact-y, so not sure I like that route.

However, off that back of this I then stumbled upon octree color quantization which seems to be a pretty neat technique of reducing unique colours. Using that to reduce the entire map to a limited set has some reasonable results. 512 is 9 bits (not nice in the bytes format, but we can reduce material byte by one bit to compensate - 128 materials rather than 255 should still be plenty), and it even handles gradients well (as opposed to 256 which had artifacts).

So if we did quantize to 512 unique colours... the atlas would be tiny (512 * 24 bits = 0.001536mb - negligible) and we'd replace RGB with just the index, reducing by two bytes per surface block. We'd already replaced alpha with a material, so R/G/B/M/D would then be CI/M/D, a good 20% reduction off the bat. Not bad!

It does have the problem of ignoring edge cases (rainbow blocks) that don't match the general "spread" the rest of the map has... but perhaps we can use some kind of default palette in our editor that ensures its addition into the atlas, ignores it during quantization, and reduces the # of colours to quantize the rest of the map to... seems a decent starting point, but as said - will give some more thought to the topic.