A bit of a revision: I continue with the idea that I had before about allowing players to control "Mercenaries" that would fight alongside them, but I think that mercenaries should be able to be bought at several locations, each location offering a slightly different version. Say, Baron would offer the player a level 1 Warrior or Healing class(Probably made specifically for the mercenary), and Kaipo would offer, say a black mage type.
Now, while I'm saying offer different kinds, I think you should be able to only have one mercenary at a time, but be able to get rid of them if you want(If you start with one, you have to get rid of one to get a new one) and if you buy a new one, they start off at level 1 again, making the player have to make a choice of whether or not they want to keep their current one, or train a new one.
While I said I'd like to see FF1 Blackmage/fighter or FF5 characters, I think I'd like to change my mind. I think the mercenaries should have icons specific(and new) for each of their classes.
This may seem like a lot, but I don't think it would be too hard to program, though it might be tedious to put in how I want it exactly. The easiest(Yet most boring) solution would be to allow players to control the mercenary as if it were an extra turn(which is what I'd prefer to have.), rather than an AI controlled one, and to only make them available in one place(Though I would rather have more than one type available.)