When optimising images with only a few visible colours, reducing the output colour space can have massive savings (Eric is talking about the Acorn software here):

When I clicked the “Index PNG Colors” checkbox and changed the slider until I started getting dithers or obvious color loss, then brought it up a notch or two, the difference was astounding. Instead of a 30KB file, I got a 4.4 KB file. Instead of saving at 75% the original size, it was now 11%.