Wenn du den Tileset auf 256 Farben reduzierst ist es was anderes, aber dann kannst du natürlich trotz vieler Tiles nur ähnliche Farben benutzen. Ich denke, da macht es keinen Unterschied welches Grafikprogramm du nimmst. Irgendwann kommst du nicht darum herum, dass Farben zusammengerechnet werden. Die einfachste Lösung wäre hier doch kleinere Maps zu benutzen.