Putting QUANTIZE_FORCE=on and QUANTIZE_COLORS=256 in your MapServer output format forces the output PNG to be indexed and 50% smaller.

FORMATOPTION "QUANTIZE_FORCE=on"
FORMATOPTION "QUANTIZE_COLORS=256"

OUTPUTFORMAT
NAME "aggpng24"
MIMETYPE "image/png; mode=24bit"
DRIVER "AGG/PNG"
EXTENSION "png"
IMAGEMODE "RGB"
TRANSPARENT FALSE
FORMATOPTION "QUANTIZE_FORCE=on"
FORMATOPTION "QUANTIZE_COLORS=256"
END

OUTPUTFORMAT
NAME "png"
MIMETYPE "image/png"
DRIVER "GD/PNG"
EXTENSION "png"
IMAGEMODE "RGB"
TRANSPARENT FALSE
FORMATOPTION "QUANTIZE_FORCE=on"
FORMATOPTION "QUANTIZE_COLORS=256"
END