I don't like the fatigue idea much but I recognise that something needs to be done to tackle kiting issues and this would help in a long game but most battles are much shorter and it does nothing to deal with the impulsive mega mage that wipes out the enemy army in his first 2 turns. Maybe spells like blizzard, fireball and dirge of ceresa need a charge up time of 2 turns? With regard to fatigue maybe a unit loses 10% of its initiative with each turn it takes, so once the unit has taken 10 actions it's initiative becomes a base of 1 and once every unit has taken 10 turns they are effectively equal? However that approach would be unsatisfactory because it will create anomolies where the faster units fatigue quicker and actually become slower than the 'slow' unit simply because they have taken 10 turns quicker - so maybe the base should be the fastest enemy unit?
This thread seems to be focusing alot on archers - I don't think they are the problem, they are generally quite weak and already get a strength and initiative penalty. To get to horse archers you need to do ALOT of research too - once the AI is programmed to use these correctly then the playing field becomes level. Maybe cap their ammo and leave it at that. TBH I would like to see different types of arrows as researchable techs - magic arrows please 
The main issue for me is how champs are able to exploit kiting to level up quickly - far ahead of the rate an empire develops. Once a champ has reached 20+ levels and you have a high mana income plus cloudwalk then you have effectively won the game. The key to reigning in the super champs is to make monster fights more challenging so that champs arent able to solo it so easily - that means giving them additional abilities to combat kiting.
Here are some other things that really benefit from a high initiative approach and may need looking at too:
1) Implusive trait
2) regeneration (very powerful with multiple life shards and multiple turns)
3) battlecry, haste and slow - battlecry can get pretty insane once you have a bunch of life shards
4) stun trait (and other dazing/proning effects)
5) I'll throw in counterattack too as it effectively gives you yet another attack, which can equate to 4 vs the AI's 1
6) anything that boosts movement
I'm not saying that these should be nerfed necessarily, just that I have been able to use all of these very effectively to really exploit initiative.
With the right combination of abilities you can effectively deny a monster any actions whatsoever and just take one turn after another in a 1 vs 1 battle. Yesterday, I played a tactical battle with my high level (30+) General Carrodus vs the big earth elemental Torax - I started by using battlecry and haste to boost my initiative to the point where I had 3 turns to Torax's one and then I kept using stun against him so that he missed his one turn and then i took another 3 and stunned him again etc - perhaps these big boss monsters should be immune to stun?