Alphonse Elric:
Next up is some kind of level for these guys I think...also, if they are both on-screen, enemies AND powerups have to share either those existing palettes OR the one remaining palette...kinda tricky. Probably won't be able to have them both on-screen at the same time I guess...and will have to dedicate powerups to one of Ed's palettes I think...hmm...
EDIT - gonna tack on some thoughts about the game as a whole here, I don't really expect anyone to read them though!
I think Castlevania II is the closet thing out there to how I'd like 8-Bit Saga to play, at least on the NES. More recently, Cave Story was a nice mix of platforming and adventure elements. Basically, you'd travel from town to town, sometimes backtracking, fighting off evil and helping to capture evil alchemists. Press the Select button at any time to switch between combat-oriented Al or magic-oriented Ed. Would be nice to incorporate casting times - like if you start a spell as Ed, you'd be able to switch to Al and fight guys hand-to-hand while the spell charges, then it would auto-swap back to Al for the devastating spell effect. Ed should be able to heal Al during down-time, but Ed would require food or drink in order to heal. Once Ed has been incapacitated he can no longer heal Al, but you won't be able to just walk around as auto-healing Al all the time - you'll need Ed's magic to get past lots of different monsters and barriers, plus his magic will be useful in combat, especially for distance attacks. Once you've helped save a town you should be able to use their tavern to get free food and drink to rest up before traveling to new places.