I have figured some things out for this idea:
Level 1-4: The 4 basic troops (Inf,Cav,Arch, and Cats)
Level 5: Players will get 1 selections from 4 types of troop that are anti-cat because catapults are the most devastating of troops without attributes. These four troops will also take more stone to train since, so far there aren't any troops that take a bunch of stone to train.
Level 10: Players get a choice from 2 types of soldiers that will be a mix between an inf and cav.
Level 14: Players will get a special unti. I saw one of a fire archer, or something of that sort. This unit will not cause instant damage but rather wears down all the troops of the opposing player. Ex. You have poison archers, when you have them attack after each round you would lose more of every unit that what you would if you didn't have the poison archer. This will effect all units of the opposing player at once.
Level 19: Players get a spy to show the techs, and levels of traps and turrets of the enemy player.
Level 20: PLayers get something called guerilla, this would sit outside your city and weaken enemy armies before they attack. I think this troop should cost a lot of crops and some people to carry the crop to them.
When going to battle you would have to select four of the troop types that you have to go to battle.
I got all troop ideas here http://haypi.com/forum/viewtopic.php?f=4&t=11925
I posted two seperate ideas but they are apart of one main idea. This is rough, so comment so I can add more to it:)