OK, where to begin. So you said you are struggling against Medium and Hard AI. Now, truly believe when I say this, that I mean no offence, but if that's the case your probably just not that good at the game yet. We all were bad at the game when we started, and really a lot of your skill will come from just playing and learning the strengths and weaknesses of each faction. That said, let me give some basic tips against normal and hard AI, then some tips for brutal.
So, firstly, the normal and hard AI do NOT cheat, at least to my knowledge. They pay the same for everything that you do. Its the brutal that can cheat. Now, against AI, they follow a similar pattern every time. They harass with some troops early on, then they hit you with a hero spam and some siege(if your on a castle map) This will happen with every AI on hard difficulty and up.
So for early game, you should focus on getting your scout hero and grabbing up some outer settlements and creeping. However, you will probably not be able to hold those outer settlements for long, so do NOT upgrade them unless you are sure the enemy is not going to attack them. Another thing you will notice with AI is that they always go for the same farm, or maybe a couple of different farms if they are defended successfully the first time around, you can exploit this easily.
Now, your next focus after you get some outer farms is to FILL YOUR BASE AS FAST AS POSSIBLE! Unbuilt plots are wasting their potential, the faster you build up your base the better your economy will be. As Gondor, you should have at least 6 economy buildings, ideally 7, and then whatever military buildings you want at the front. As Rohan and Dwarves, you want 5 economy buildings, and an upgrade and military building. As Mordor and Isengard, you need 6 economy buildings, then 2 military buildings for Mordor, and 1 uruk pit and 1 armory for Isengard. Don't get wargs they are awful.
Now, as for your economy buildings, you should upgrade them based on what you need. If the enemy has the entire map and you are unable to take map control, get pantry 1 and resources 2. If, however, you have lots of good map control you may want to get resource 1 pantry 2, and build a big army. You should never put anything more than pantry 1 on outer farms, as they are so vulnerable for such an expensive upgrade. Also, NEVER get defensive measures, its a waste of money, especially against AI. Better to just get resource 2 and have the farm pay back what you spent quickly. I generally go for double resources on my outer farms close to my base, and pantry 1 resource 2 on the rest of the map.
Now, what troops should you get per faction?
Mordor is the easiest, get 2 orc barracks and spam spam spam.
Isengard can prove difficult, if possible try to get a Wildmen Hut and keep it alive, use it to get Wulfgar and spam some wildmen out.
Gondor is also pretty easy, you want a signal fire to get troops, try to protect it behind your base if possible, and then make a barracks and archery range. Now, I personally make 6 townhouses to get the full discount on tower guards, immediately upgrade my barracks and start spamming those, however some people prefer blacksmiths, so that's up to you.
Rohan is another easy one, just get Corrupted Théoden quickly and use his cruel taxes on an outer farm. This will make it produce more resources, and it will also upgrade faster and train troops faster. So use cruel taxes, upgrade it twice with production, then start spamming out those peasants. Make sure to effectively use Theoden's traitors ability as well.
Now for Dwarves. Now, your sub-faction depends on what the enemy AI has as their faction. If the AI is Mordor or Rohan, you want Iron Hills. If the enemy is Gondor, Isengard or Dwarves, you want Ered Luin. The reason for this is Iron Hills early game is much stronger due to their guardians having the charge ability, while Ered Luin is very strong late game because of their OP heroes. You want to get a travel camp behind your base and get veterans ASAP. That should be your main priority behind filling your base.
Now for all factions, if you invest in a hero, you CANNOT let him die. Losing a hero is a fatal mistake against AI. Fortunately, since the AI frequently targets your heroes above all else, you can easily play ring around the rosie with them. Use the hero to kite the aggression, and keep running him around your base while the towers pick the enemy to pieces. Additionally, AI absolutely LOVE to spam siege and try to kill your base with it, if you can get cavalry(except wargs) do it, they are incredible siege killers.
Now, tips against Brutal. Brutal is tough, no getting around it. Some maps make the brutal AI incredibly tough. For example, try beating a brutal Isengard on Fords of Isen 2 as Gondor. It is no easy task. However, know that Brutal only pay 50% for everything, and I believe they also make more money than you. Nonetheless, as I said above they follow a pattern: small early game harassment, hero spam, siege spam. If you can survive the first hero spam you have basically won the match. Against Brutal, you will be completely unable to hold your outer farms, you must try and survive in your base until you have enough heroes and some upgraded troops, along with spellbook powers, to push the enemy back and take map control. Losing heroes is a death sentence. If you are on a castle map and have walls, you want to get wall catapults if you can spare the money, to snipe the enemy catapults. They will almost always go for your gate first, so keep this in mind. Hope all this helps