The addition of flying units that could only be hit by rangers and dragons and ice mages would be an excellent addition and could add something to maps.
Burrowed units that can only be hurt by swords from zerkers and knights could also be an excellent addition.
Both of these shouldnt be used as forcing a certain play style on every map, but could be used as gimmicks on certain maps.
Just something to consider.