I have played a few games over the past little while and noticed something. In pretty much every game I pay 1-2 AIs end up stuck on a little patch of fertile land with only one city and no natural expansion. These AIs usually end up stuck in the middle of nowhere and end up doing nothing, and this isn't very fun. Not having access to at least 2-3 cities is the touch of death.
A simple solution that would really help the AI, make maps and victory less random, and increase player interaction would be to make the initial settling of a city done by a Sovereign spread their environment a distance equal to the minimum distance between cities for that map size. This would ensure that every player had a natural expansion pretty much every game, and help prevent a player from being completely cut off from everyone else by a huge wasteland. It would also be completely in line with lore and existing game mechanics.