The aspect of the game I enjoy the most is when you get players working together. Two ideas to increase this:
Maps that force trade - e.g. one player has all the mana, another the gold, others face the zombie horde for immediate valour.
More player specialisation. What if one player has crowd control, another ranged troops, a third defensive strength, another massed steamroller? They would need to cooperate closely to win. I know each race has these strengths, but currently I (and most players) take a mix of cards from different races to create your own balanced force. What if you could only get balance forces through cooperation? The game could become a coordinated dance…Would need to start with a couple of towns so you dont have to walk miles before cooperating.
Combining these two you could get a very different type of game, where you have to work out and execute a joint plan. Wouldn’t want this for every casual match, but especially one the clan system kicks in. Could be achieved through map design,start towns and some restrictions on what cards you can take, or what sort of towns you can take over…can an elf player take over a dwarf town?