When you reach the end of the game where you have to scale the mountain a third time to fight Kala, you can go to your inner realm and get quests from all of your friends which make them slightly stronger and unlock a 4th palette swap. They will generally have fairly clear instructions on where to go, but since you only need to do one, I'll give you the one that was by far the easiest: Phoebe.
If you didn't unlock Phoebe, she's standing around the port town Maerifa: giant Purple-haired woman. It's a very short quest to get her to join you once you talk to her.
Pheobe's resolution quest is simply to talk to her kids right outside the Tower of Wisdom in Maerifa, then meet her outside town in the desert for an extremely easy fight. The entire process should take only a minute from any fast travel point, since the tower of wisdom has its own warp.