I've seen plenty of people in ModDB complain about the difficulty of the AI in version 4.2.1, and supposedly the AI is even better on 4.3. Whether the AI difficulty should be reduced or not, that depends on the difficulty level, IMHO.
* Brutal: the AI is supposed to be brutal, so no, don't make it easier. Make it even harder.
* Hard: I'll need to play some more 4.3 until I can comment on this one. According to 4.2.1, though, I don't think Hard AI needs to be nerfed.
* Medium: Seems fine so far. Not especially hard, but they can wreck you if you don't know what you're doing. Shouldn't be nerfed, either.
* Easy: I admit, I've never played against the Easy AI in 4.3. However, according to 4.2.1, definitely nerf this one! Easy AI is sometimes even harder than Medium or Hard AI, as factions like Gondor just rush you by spamming their cheapest units on Easy. I still think there should be at least one newbie-friendly difficulty level, so that beginners don't have to cheat and use handicaps to even defeat an Easy AI. Personally, I'd nerf the Easy AI so that they'd never build siege. This way, you'll still have to face their unit spam, but it's actually very hard to lose against them.
IMHO, the hardest part of the AI are the first 15-20 minutes, as their cheat money gives them an early advantage. When you get your economy set up, get a few heroes out and start getting upgrades, you've pretty much won the game, and the rest of the match is mostly just regaining map control. Note that starting with 4000 credits makes the AI a lot easier, as you'll get your base filled up and/or get some heroes out right away. I usually play with 1000 credits, though, as early-game creeping is fun.