Unlike others, I love not having maps.
However, I see a great opportunity to make maps unique.
Force people to tan a hide, and use charcoal or squid ink to draw their own map (collecting bottles and corks would be cool too). Now, making them draw entirely by hand doesn’t seem fair (especially for controller players). But make them choose the distance between islands at least.
I don’t know if it would make sense to let them select a profile of an island from a selection that had been procedurally distorted. But at least try to capture the old map feel where everything is misshapen.
I think it would add a fun element to the game to make the exploration feel more authentic and less like a computer is holding your hand through it.