Finding the right map:

The feeling of choice matters. (1) forces the player to make game style choices early in the game. Not all nearby objectives should be immediately attainable and force the player to choose what they feel is important.

AI pressure should increase as your economic and military increases (2). The AI isn't as smart as a human, so the balance should be that you are typically out-gunned to force you to out-play. A great example is playing the 1.0 version on River of Life with AI as Azracs.

In an ideally stretched conflict, unit health becomes a factor in how to deal with tactical battles, forcing you to decide how to use the terrain as cover for units, when to use gorilla tactics to eliminate siege weapons before they reach your
cities, and when to abandon or ruin a city for more favourable positioning (3). Map design to encourage little tricks like building towers to block bridges is an enjoyable and less commonly explored game element.

The game should never allow one-trick-ponies (4). Building a wall shouldn't completely halt AI progression. Producing one wraith shouldn't be the solution to destroy 20 armies and take 90% of the opponent cities. Having a tilting point where an achieved objective drastically turns the tide in your favour is good for gameplay, but because the AI doesn't adapt to enemy army composition it's better to limit these availabilities (wraith, air-galley, and air-elemental). The game shouldn't feel like you have to pull your punches in order to make it challenging.