Der Umweg übers Einfügen in ein 256-Farben-Bild leuchtet mir nicht wirklich ein...

Zieh dir doch einfach IrfanView - mit um die 800 kb wirklich nicht groß, und Farbreduzieren ist damit kein Problem. Das Bild in normaler Farbtiefe speichern, mit IrfanView öffnen und die Farben auf 256 verringern... das erstellt dir dann auch eine angepasste Farbpalette.