I would go in a different direction, in ways I think many would cringe at. Because to me Fallen Enchantress is done and that game satisfies me in what it does, so I want a new and different game. I'm just going to go on a brainstorming rant and see where I end up at. Long meaningless post coming, read at your own risk.
I would love a new fantasy kingdom game, but I would want a different one than any that are already out there. Not completely different, and certainly derived from aspects of other strategy and tactic games I have loved in the past. I don't need another game like Fallen Enchantress, I have that game and it's good, I don't need another game like Warlock, Civilization or Crusader Kings, I have those too. But, some aspects of those games could be added and combined to make a game that isn't out there and I think people would enjoy. I would prefer high fantasy, doesn't have to be Dwarves and Elves, but there are some advantages to using those. People know those races and understand them.
Multiple races, and cultures. Humans are different all over our world, we look different, worship different gods, and do things in different ways. Fantasy races should have that too. Dragon Age had some of this, elves and dwarves had different cultures depending on where they lived. In many games, there are rarely any different cultures among races or all races tend to have once culture. I like the ideas of a strategy game that have to struggle with the issues of culture, migration and immigration, different religions, and diplomacy with different cultures.
I would have one very detailed map, not random maps. One map, one world, one lore. Think Romance of the Three Kingdoms, Crusader Kings or Brigandine, to a certain degree. One map, one place. A single, focused map can give the world real meaning. Wei, Wu, and Shu in the three kingdoms are great examples of factions. Shu in the mountains, Wu in the riverlands and Wei in the plains. Their special troops and abilities played into their geographical strengths. The same could be done with a fantasy model. Dwarves in mountains, Elves in Forrest or what ever races used could be tied to their part of the world and their bonuses would have meaning. Random maps, and even built maps from a random generator lack aesthetics and meaning. Continents don't resemble any real place, hard to be emotionally attached to a place seems so irregular and gamey.
They have memorable leaders and memorable champions. In Romance, the champions had different personalities. Lu Bu was brash, brave and traitorous and Zhuge Liang was cool, calculating and loyal till the end. I think a game where the nation has at least a few assigned champions would build it's lore. Also what this would allow for are dynamic story and interactions. Building and fighting armies are fun, but there is also a great deal of fun from politics. Internal and foreign politics from games like Romance or Crusader Kings. The people who serve your king have their own motivations, so me are loyal, some are not or only for the right price. Some seek out justice, others fame and glory.
I love the concept of a ruined world being rebuilt, but I think that Elemental really did this concept poorly. I felt more like a colonist trying to survive on a previously uninhabited world. There was little rebuilding of the old world, and just building. In Romance you are in a land during a civil war recovering from a dark ages and massive peasant rebellion. In the earliest time line of the game, most of the cities are in a state of decay and are not under anyone's control. You can expand your influence and land by ways other than warfare, expanding into old, ruined cities or forging into new unsettled lands. But even then it should only be in select places that would make sense for a city to be. I'm iffy on that, I think that city building should be limited to only predetermined areas, but could be either rebuilding old cities or founding new ones in predetermined spots.
Because we have a single map, factions in set locations, champions assigned to specific factions we now have the layout to add story and plot elements to the game. Character interactions, some they love, some they hate, those that are rivals or enemies. Loyalties and betrayals, families and conflict not just from the concept of "Me red team, you blue team, we must fight till one is dead!" mentality.
Hexs. They are better in strategic and tactical battle and movement, and aesthetically far better looking.
Combat. When armies do collide, how should they fight? This has been a weakness with the Stardock games I have played, good strategic but very bad tactical battles. And a lot of romance games had pretty bad or overly simple tactical battles. What games have good tactical battles? The new XCOM and Final Fantasy Tactics, along with Brigandine come to mind. But of those three games, only Brigandine had any real strategic gameplay. Does the game even need a separate tactical battle mechanic? It depends on what game you are really trying to make. If you have a great deal of depth, the actual combat needs only to be functional and make sense. I doubt a lot of people play Crusader Kings due to how fun the battles are. Warlock doesn't have a tactical battle map, but it's a game that is meant to be lighter and faster and streamlined. I don't want that game, I have that game and Warlock does what it does just fine. I want medieval fantasy combat tactical battles more in line with the three previous games I mentioned, XCOM, FFT, and Brigandine. Most people don't know Brigandine, think Romance of the Three Kingdoms mixed with Ogre Battle and Shinning Force. If there is to be tactical battles, then there has to be tactical conditions, like meaningful range of weapons, meaningful terrain, flanking and line of sight. Otherwise, don't do it at all.
Creating your own unit was a fun mechanic and I loved it. That being said, it's not for all games. It made the units and races of Elemental bland. You can create your own units, but they all tend to look alike so I am not entirely sure what I really gained from it. I like the idea of being able to equip my troops, but I don't necessarily need every piece of their armor to show on the unit. It's just too limiting visually overall.
One fun thing in a Romance game and Crusader Kings was the ability to start at different points in a timeline. The sandbox nature meant that things start this way, but who knows how tings will proceed. I think a fantasy game could have that too. So we have our little city states and kingdoms building back from a Dark Age following the collapse of a once great empire, building and rebuilding, expanding and developing. Like in Romance, the early years would be filled with many small kingdoms and unused ruined cities, and the latter dates would have fewer, larger kingdoms encompassing larger territory. Also, like in Romance, you could create your own faction and champions to play and have them start in one of the unused cities. In romance, you could build dozens of champions and factions and multiple to your map, you could create entire family lines, husbands, wives, children, brothers, etc. Although a more dynamic one where people are born and die like in Crusader Kings would be better.