Hello, my view is that overland spells are a visible and tangible indication of a sovereign's personality. You could be using this more effectively, IMHO. I raise these suggestions because I see how you've tried to create leaders with different personalities, and think this would help you.
I use Master of Magic as an example: in a game of MoM, you'd know that Jafar was nearby even if you hadn't encountered him yet, because you'd see his sorcery spells going off at the edges of your fog of war. On the other hand you'd know you were facing a militaristic foe because they'd create more units but cast fewer spells.
In the examples above, the former relies on visual displays of magic: i.e. AI sovereigns should not be shy to cast overland spells and should do so more often. The very spells they can cast will indicate what you're up against. The latter might be linked to starting attributes: if a leader has 'warlord' attribute, then they'll rather spend money on building armies than city improvements, for example.
This game is sure to be a classic, but I would like to see a lot more overland / global magic being used by sovereigns (e.g. using tornadoes on your army, or raising mountains if your city is near their border and they've got no city in the vicinity, etc). There are few better reasons to declare war on an opponent than the fact that you're spending all your mana flattening the mountains he's raising nearby; or continually dispelling his Curse City spells. This may require more custom code that determines how sovereigns should use specific spells, which might be an addition to your generic spell-casting AI currently in place (if that's indeed how you've coded it).
Also please bear in mind I've only played on Medium so far (with a few AI's set to 'challenging' per scenario), so there may be more to discover on these aspects; but the challenging enemies I had didn't seem to use overland magic much, hence this post.
edit: I've also seen posts by other people on this board saying they'd like to see your magic system 'go big' - powerful global enchantments; a complex dispel/disenchant/interrupt/counter-spell system; multi-turn casting times - and I think that I really agree with their views.