So, I finally used my Elemental bonus and got the game at a slight discount. Well, at least they had the decency to admit E:WoM wasn't their best release ever.
...anyway, I played the game a bit and must say it is really a large leap forward compared to Elemental. It still feels like there would be MUCH more stuff to add, but the gameplay experience is okay. I can certainly sense the Fall From Heaven Influence here - in a good way. I haven't yet managed to finish a game, but all in all it seems like a solid game for the 29$ I paid.
I like the way the "neutral" factions are handled. Unlike in Warlock, where you had to visit other planesvia portals, Fallen Enchantress manages to add these menaces right on the regular map. I played on beginner difficulty, so I guess monsters and AIs were much less aggressive. Even with my level 12 heroes and 3/4 of the tech tree done, there were still larger parts of the map that I didn't dare to explore any deeper. I wonder how large maps will turn out...
Another interesting and RPG-ish thing is the way the game handles your heroes: Should your sovereign be killed, he or she will teleport back to the capital in exchange for mana. If any other hero is "killed" in battle, the game considers him wounded and adds a permanent(?) random wound (lost and eye, broken nose, limping leg, etc.) with negative effects. Thats actually a cool way to be lenient AND to increase the immersion at the same time ("See that eye lad? Lost it when we defeated the ashen dragon in Turlia valley").
The map is also gorgeous (like it was in Elemental) and the addition of small icons for special sites was a really good thing. Bot clothmap and 3D map are well done. Just missing my CIV5 hexes a bit...

Also the map changes as your influence increases - in neat way to show that you have influence on the world itself: Land becomes fertile in kingdoms, wild forests turn into serene woods, badlands turn into grassland. You wouldn't even need any border display - the map visuals already show perfectly where your kingdom's influence is spreading. Empires seem to do the opposite an desecrate lands and turn them into purple and blue-ish wastelands.
However, I have to agree with a thing said above: City building is certainly not as complex or full of choises as in other CIV-like games. There are a few situations where you have to decide things (for example, when specializing the town, chosing the reward for the next town level - another great idea, btw - or try to grab a "wonder"), but most of the time, I just go material (= hammers) > food > gilden (commerce).
Combat is also a bit repetetive - no comparison to HoMM. But: With all the cool stuff you can find and all the skills you can learn, you really get a good feeling for the progression of your heroes. The troll that was a deadly enemy at level 2 with your crude bows and swords is only dangerous in a group against your level 8 heroes with their shiny artifacts.
All in all I think this game is not so much about creating a large empire. It is more about role-playing your struggle in a rough post-apocalyptic fantasy environment and slow step-by-step expansion as you recover old knowledge that had been lost. More about immersion and feeling than effective strategy and perfect turn planning.