I'm enjoying playing FE:Legendary Heros, but after a few play-thrus, the games are feeling the same.
What might help is having more variation in how the AI opponents and factions (and more options for the player):

Some ideas/suggestions:

1) Deeper technology tree
   - by the end of a game, it's possible to research most of any one tree, and much of all the others.  Most games have the same technology researched; each faction plays similarly from game to game, and each faction has fairly similar equipment and units.  The tech tree has the same options each game, and for each faction (with small variations between empire and kingdom).
   
   a. Would it be possible to have a larger tech tree, such that it impossible to research all of it (or most of it) in one game?
   
   b. possibly with some of the tech trees to be exclusive (for example, if a faction begins researching a necromancy branch, it closes off other opposing magic or tech branches)?
   

2) More unique faction spells
   - same comment as above; the more unique the spells associated with a faction, or with the spells on one of the tech branches, the more unique each faction plays, and the more replay value the game has.
   

3) Faction-specific city level-ups
   Instead of just the three choices every time a city levels up, could a 4th option that was faction-specific be added?
   For example, the Tarth will likely have some different buildings than the Oracle, and this will help make each faction feel different.


4) More late game challenge
   - surviving factions teaming up against leading player (esp kingdoms vs empires)
     - (similar to late-game option in Total War: Shogun 2)
     
   - more aggressive AI: if player gets ahead, AI doesn't seem to want to attack
     (at least in a 6-player game against AI opponents).  The AI threatens, or demands tribute, but seems to be passive, and takes little action (this is on hard/challenging/expert, using medium or large maps)
     
   - with a larger tech or spell tree, other factions could be pursuing different end-game goals or tasks that could force the user to take action (to prevent summoning a large creature, for example, or fighting over the pit of voices, which I've never seen the AI investigate). 

Currently, if you can get a significant lead in points over the AI players, there isn't anything that is going to push the player hard; they can control the pace and action.


5) Faction-specific goals
   Similar to the faction goals in Fall From Heaven 2...  each faction shouldn't necessarily have the same goals and motivations.  The greater the difference in how each AI faction plays, and how it plays from game to game, the better.

Thanks-