In warlords 3 units that fought in a battle had the chance of gaining a medal. In warlords 4 they took it further and made units upgrade in interesting ways after getting a certain amount of experience.
Right now a unit recruited at a city is just as good as a unit that has fought in 20 battles. This isn't realistic, because green recruits are not equal to battle-hardened veterans.
I think it would add another dimension to the game to have units gaining power by surviving battles. It could take some of the edge off the breakneck expansion that is currently rewarded. Because losing all but one unit to take a city may not be the best option in the early game.
Maybe some of the more powerful units aren't so mighty when produced from a city, but become terrifying after gaining some levels.
IE a dragon could emerge as a hatchling or a dragon whelp and grow into a full fledged dragon, you could express this growth with several color shifts. So hatchling->dragon whelp->young dragon->green dragon->red dragon. Strength, abilities, wounds and movement could increase with each new level.