Magistr, тогда у тебя один путь - загрублять картинку, уменьшая число цветов. В GIMP в опциях сохранения PNG можно установить сжатие - ставь полное, а все остальные опции выключи.
Почитай о PNG, чтобы лучше понимать, с чем имеешь дело.
http://ru.wikipedia.org/wiki/PNGНапример, там сказано, что используется алгоритм сжатия deflate. Можно отталкиваться от его особенностей.
Различные реализации алгоритма Deflate дают разную степень сжатия, поэтому были созданы программы для пережатия изображений с несколькими вариантами настроек в целях получения наилучшего сжатия — например, форк pngcrush OptiPNG и advpng из комплекта AdvanceCOMP (использует 7-Zip).
Если цветов на картинке не более 255, то можно включить режим палитры.