How about this: not having an 'unlikely' hero, or a kid hero. How about having someone as the main character who is actually already experienced in heroic type activities. An adult, rather than a kid. Ever see that in FF? Not recently at any rate. The adult roles seem to go to the supporting cast, but it'd be nice to see the hero have a surfeit of confidence, which most of the ff heroes seem to have lost.
For example, have an Auron sort be the hero.
That might provide something new. Other than that... well, don't look to me, I'm not a good story writer. Heh. Most of my storylines borrow heavily from ancient writings. Which I suppose could work. I mean, adapt the premise of the Seven into a FF game? Hey, could work. You could have the protagonist be a hero or prince who is rallies the other heroes to him in order to fight his brother who has outsted him from his throne. His brother, however, wouldn't be 'evil', per say, and it could have a great deal of ambiguity as to rightness. All along you could have skirmishes between the supporting heroes of the one brother, and those of the other. Things like that. Or the hero needn't be one of the brothers, but maybe only one of the supporters.
Basically, it could involve not finding some super items, or killing a really evil arch-nemesis, but finding (and selecting?) the seven heroes that are your allies in your endeavour. Something like that. The setting could be whatever. It doesn't have to be set to any one thing. But one thing I think that FF must have is more choice. I think you really have to be able to choose - decisively - which characters will be with you and which won't. Have more variability in the main character towards better or worse inclinations. Seriously, how hard is it to do this? Good grief, I can do simply triggers like that on an old RPG maker... if I can do that, I'd wager SE could do it with FF. RPGs have gotten way too linear it seems. I mean, it's a simple choice, but even the 'fight/join' decision with Magus, or the 'save/leave' Crono one, made CT really interesting. I think FF needs to start doing things like that, and actually allowing you to make decisions that affect the gameplay.