Recently I've been able to reduce my download overhead by up to 80% (though overall about 50%) through further reducing outputted image palettes, then rerunning through PNGOUT, OptiPNG, and DeflOpt.
Here's an example of quality loss and size difference (the size difference is even before running through PNGOUT, OptiPNG, and DeflOpt):
<img src="http://i.imgur.com/PD6sb2x.jpg" border="0" />
Of course many images don't work at 16 colours, but many do at 64 or 128.
I'd imagine that the dialog could look something like this.
<img src="http://i.imgur.com/MOisC41.png" border="0" />