[Sandman]

If you own the capital of R'lyeh, a dominion kill should be possible. Start preaching and building temples anywhere where R'lyeh's dominion is left.

The sailing ability is, IMO, more useful on player-created maps with complex coastlines than random maps, which usually have large, round seas.