Well, I'm not quite sure if i'm gonna use Magus...Ayla is already replaced. Also i'll try to change the palettes of the heros in SNESPal but idk where there palettes are located Oo. So may take a bit :\
The palettes for the overworld sprites, or the main sprites?
The main sprite's palettes are already found and listed in Geiger's offsets.txt
240000 2417B7 PAL No No "Character, NPC, Enemy palettes (12 colors each)" 7/8/2003
The main characters' palettes are first.
Snespal also has a color search feature, just snap a screenshot in Zsnes, choose a color, and search the ROM with Snespal for that color, it lists all the matches. Just edit the ones that look about right, save, check the game to see if it's the right one. (do this on an extra non-important ROM). I've found every palette I've searched for with this method, in many different games. Don't use Snes9x for this, the colors displayed are off, or something. (by screenshot, I mean Prt Scrn)