it's not even 256 colors it's 64 colors. 256 colors would be 1) too slow and 2) too memory expensive. So using 32 colors would be just dividing by 2.
So EHB could be an option?
EHB would need special processing of the palette (color quantize would not work) and we'd lose the sprites OSD & background layers in stages 4 and 6. Plus no AGA means 16-bit fetch not 64. Seems a lot of trouble for a not so good result.