I understand the real problems are the two first, since doubling the initial size would be problematic only for slow computers -which could still play selecting a smaller initial map. I hope the idea needs not to be definitely abandoned, though. The other two reasons should be possible to overcome, I actually remember an old game -Masters of Might and Magic?- that had two worlds (the normal and the "Myrror" world) and gates that linked them. The AI was probably very simple, but if they could do it, why couldn't we?
With respect to sea units, I don't think it plays worse than in vanilla... but that just means it sucks. If you own an island you are pretty much safe, which shouldn't be. I wonder if it could be possible to teach the AI to prepare and launch invasions. The script, if implementable, could be simple and yet make the difference. The algorithm would need to determine:
For every coastal enemy city:
a) Amount and mix of land troops appopriate to take it
b) Number of transports required to send those troops
c) Number of defense vessels for the transports
d) Tile or tiles to disembark (close to the target city and easy to defend)
e) Path the transports and escorts should follow
f) Intrinsic value of the city (from size to wonders and defense bonus)
Once done for every city one should be selected and the construction of the appropriate land and sea units should begin (unless the AI determines it is suicidal, in which it should focus on defense). That can be recalculated every turn so that if conditions change the invasion might be done with fewer units or to a different city. Now I understand it can be difficult to weight a shorter path versus a more defended city, for instance, but I feel that this addition, if implemented, would have a huge impact on the game (and it can always be tuned and perfected later).
Again I don't know if this is doable or even accesible from the sdk or python, so please excuse my excess of optimism if it is imposible.