A living world sounds good, yeah. Also having neutral creatures pop up depending on the terrain type (i.e wolves and trolls in forests, deer and centaurs on plains, bears and ogres in hills, etc), so you can get items like fur and bone to use to make armour and weapons (at least until you learn metalforging). Neutral units would also help the undead get corpses so they don't kill the other races' starting civilians.
What would be great would be a skill system like this, but I don't know if it would be possible in Warcraft 3 (or how easy it would be to make) :
Each villager who is born has a random level 1 basic skill (and possibly a trait, i.e Intelligent, he picks up new skills quicker, or Fast, has a quicker move speed, or Brute, has higher attack, or Stout, has higher HP) when he/she becomes an adult (maybe woodcutting or mining or hunting). He works the best at this activity. Over time, he picks up EXP in the skills he performs, and learns new advanced skills (which can only be performed by units with the appropriate skill).
Maybe if a woodcutter is assigned to mining, he might eventually pick up Mining Lv 1, and combine knowledge of both and pick up Stonecarving Lv 1. Then he can carve spearheads, and might pick up Stonecarving Lv 2 in time and be able to carve axe heads. He might also pick up Woodcarving Lv 1 and learn to make spear handles, and then Woodcarving Lv 2 and be able to make axe handles. Someone who spends time making weapon heads would in time pick up Weaponmaker Lv 1 and be able to combine spearhandles and spearheads to make spears. Once their skills reach Lv 2 or 3 they can begin to teach the skill to other villagers who recieve Lv 1 of the matching skill.