Here are some ideas, mostly drawn from the new King's Bounty games (and one from Battle for Wesnoth):
http://sourceforge.net/projects/fheroes2/forums/forum/335991/topic/3948917
Talent Trees: http://sourceforge.net/tracker/?func=detail&aid=3112477&group_id=96859&atid=616180
Scripting ability for multiplayer maps/campaigns: http://sourceforge.net/tracker/?func=detail&aid=3112479&group_id=96859&atid=616180
Initiative being separate to speed (not all of this one are relevant to Elemental): http://sourceforge.net/tracker/?func=detail&aid=3117491&group_id=96859&atid=616180
Buyable Locations to protect Castles: http://sourceforge.net/tracker/?func=detail&aid=3112461&group_id=96859&atid=616180
Neutral Locations in Non-Castle Battles http://sourceforge.net/tracker/?func=detail&aid=3112455&group_id=96859&atid=616180
Not all of them are totally relevant to Elemental, or even to H2, but it could be cool for battles <inside> artifacts, or artifacts that have morale that could change based on certain priorities of that artifact (and a fight required if you want to use the artifact's abilities again if morale falls to 0). Also "many more special abilities with charges per battle/reload times to make different troop types much more interesting", and "having treasure either you or the enemy can pick up in the battle screen (if they pick it up, you don't get it)"
, different sized and shaped battlefields, and more.
And of course dungeons to visit, custom quests with big bosses with special attacks and special rewards for defeating them. 
What do you think?
Best regards,
Steven.