Advance Sprite Palettes

Try searching the GBA ROM file for this combination of  bytes in a hex editor.

Code:

02 01 04 04 00 00 00 03

That's the list of palette ids for the first 8 characters. I found it in 2 places in the US GBA ROM. Try replacing index 4 and 5 (the first two zeroes) with the palette id you want for Edgar and Sabin. I think it should be 01 to get the brown soldier. That should change the palette that is used in battle. I might be able to add this to FF6Tools, but in the mean time it's pretty easy with a hex editor.

You can also search for this in a save state or sram file. I think it's stored in the same order, even for a GBA save state. That should change the palette used in the field and menu without having to start a new game. Note that this is in addition to changing the event script as Gi Nattak explained. In the US GBA ROM, Edgar and Sabin's palettes get set at 0x7A66B2 and 0x7A6D21, respectively. You can change these with a hex editor or with the event editor in FF6Tools.

Another thing, and this is going to be a lot of work, Edgar and Sabin often show up on maps as NPCs. The palette and graphics id for NPCs are stored differently from characters. This is how e.g. Gerad has a different palette from Edgar. This means you would need to go through map by map and change the palette and graphics of every Edgar or Sabin NPC you find. You can do this with FF6Tools. I would recommend doing this on a fresh ROM and then creating an IPS patch to copy the changes to a modified ROM. That way if you screw anything else up in your modified ROM later you won't need to do it all over again. On the other hand, if you later insert or remove any NPCs your IPS patch won't work properly any more.

Hey thanks! That worked perfect! Sorta.
I couldn't find that string in the save game or save states, but I did find them in the ROM itself.
Changing the numbers as you mentioned changed Edgar and Sabin's palettes in both the party select screen and in battle, but not in the airship or on the overworld. But that's a great start. Thanks!

I don't suppose you would know which numbers change Cyan and Shadow? Since Ive settled on changing THEM into Biggs and Wedge already since their color palettes looked better than any of the others. (Cool black uniforms)

Never mind! I figured it out! It appears to be those first two 04s in the string you posted! XD Perfect!

In FF6Tools, when you click on Character Graphics, and go to where you can use that drop down menu on the right to select what color palette to display as, there are 4 weird color palettes there. They are simply named:
Palette 27
Palette 28
Palette 30
Palette 31

Palette 28 is a weird sort of shadow palette that makes whatever sprite is loaded semi see through. The rest are all just this ugly solid puke color. Would it affect anything If I replaced these palettes with other ones? Are they actually used by anything in the game or are they just placeholder palettes that can be overwritten for me to add content?

In FF6Tools, when you click on Character Graphics, and go to where you can use that drop down menu on the right to select what color palette to display as, there are 4 weird color palettes there.

They may be used, much like the rest of the palettes. I don't think someone ever discovered some palettes were unused, and as far as playable characters goes I think you can only assign palettes 0-6 but I could be wrong.