Not sure if this has been suggested before, but it would be fun to have some underwater areas (shipwrecks or sunken loot on ocean floor), as well as random spawned shipwrecks included in gold hoarder voyages. Basically just make the whole map a possible location for voyages.
