One thing to keep in mind with Deity/archipelago/domination is that while it's harder to get moving earlier, there's also much less need to. You can wait until turn 250 or so if you wanted to before you even declare your first war. This is because:
1.) late game ships can move 5 or 6 tiles per turn and no tile has negative terrain movement modifiers.
2.) Domination requires taking only capitals, and all enemy capitals on archipelago maps are coastal. Therefore, since the units can move faster, aren't affected by Great Wall, and don't encounter movement penalties, you can almost always attack just capitals. Sometimes there's some land choke points that require an extra city to burn to get through, but this is so much faster than land maps where you almost need to plow through every tile of land and all cities in the way before you reach each capital.
3.) AI's incompetence at naval combat.
These three issues allow a player to go from peaceful-all-game to conquering every capital in a few dozen turns.