Nein, Photoshop ist nicht Freeware, ganz und gar nicht. Teures Programm...

Noch kurz zum Problem:
Paint verwendet beim Exportieren in 256 Farben die originale 256 Farben-Palette um. Mit anderen Programmen wird eine Palette mit den benötigten, oder zumindest einer Auswahl derer, zusammengestellt.
Deswegen ist Paint für solche Dinge ungeeignet.

Abhilfe schaffen da Freewareprogramme wie IrfanView.

Wenn du den Deutschpatch hast, kannst du mit klick auf Bild -> Farbtiefe reduzieren die Palette umstellen.
Das Floyd-Steinberg Dithering sorgt meistens dafür, das die neuen Bilder im Endeffekt besser rauskommen.

Eine weiter Alternative wäre natürlich auch The Gimp. Ist auch kostenlos, allerdings etwas komplizierter.