I remember the "Medium" Age of Kings AI.
Let's just say that it wasn't medium at all, more of a "git gud" test of your skills. I see our "Medium" AI in the same light.
The AI has improved, but it's not "too difficult", I've won my last couple of Matches on Very Hard, and I suck at playing, I have never seen a video of what to actually do, and I don't care at all about mechanical playing really, I just boom the economy, build defenses, and then attack, all quite slowly. Now, it could be that Normal is indeed too difficult for newbies, but I disagree that this means, as mentioned somewhere else, that the AI or the game are intrinsically too difficult, the issue would be just with labelling. I think that what is artificially labelled as Normal should be equivalent to Normal in other RTS, if the idea is to be friendly with newbies, otherwise it seems to me just a pretentious semantic problem. Level naming has to be adjusted to RTS players, all of them, not just the vast minority that play competitive online matches (something I see as a recurring issue with this game). One could then keep adding levels anyway if more range is needed, to give a challenge to everyone (Extremely Easy/Hard, etc), and the most pros can always try their luck with a 1v7.
This didn't look right to me, so I checked: that's not a real Maya symbol, but a Mayanism one (New Age stuff), funnily enough based on an Aztec symbol. You can see the original Aztec one on page 13 of this scan of the Codex Magliabechiano: https://digicoll.lib.berkeley.edu/record/289019?v=pdf