Imo, adding ships to the sandbox mode would be a massive undertaking if the intergration of seafaring is going to be successful in the remotest.
I would rather see the sandbox mode have an option to activate north-south world wrap and east-west world wrap so that no matter where you start off in random world, you are at the 'center' of attention.
This change would require considerably less effort to undertake. More stamps would need to be created so that the edges are traversable. Some programming needs to be done so that the game can't tell the difference with the map edge, as if it were normal terrain always. Done.
Toss in some flying spells and waterwalking spells and properly adjust raise/lower terrain spells and presto....no more need for ships to overly complicate the game.