The AI tends to send their Sovereign in by himself for some reason ... Gilden did that to me (but I think it was on normal).
As for AI starting really close ... is this intentional? To allow a rush for rush players? Or is it something that should have a natural block in the map-gen code.
Likely, this is as good as its going to get (as Civ had similar problems even in IV, I think its just a map gen problem in general)
That being said, in my one game I started a good deal distant from any AIs 