Design issue - the game is rather predictable and does not have any ‘twists’ that could make it more exciting.
Suggestion #1 - Add ‘Discovery’ locations to the map (ruins, temples, caves, etc.) These locations yield opportunities to recruit unique units, acquire new cards, add experience to the first units that land on the location, add resources (gold, magic, valor) or unleash new foes if the player is unlucky.
This also adds an opportunity to add the ability ‘explorer’ to some units. These units increase the odds of getting good things from the ‘discovery’ locations if they are the first unit to reach the site. It also opens up a new item to discuss in the diplomacy arena as players negotiate who should explore the location and reap the possible benefits.
Suggestion #2 - Add some protected neutral locations to the maps, ones that do not wish to join the players willingly. The players must defeat the protectors before claiming these locations.
This kind of location would add the opportunity to add a ‘diplomat’ ability to some units. These units would be able to convert these neutral locations without having to defeat the protecting forces.