Kind of a major stretch but I already put many ideas in the forums so why not this one? xD
Mega-Megalodon/Whale Forts:
So basically a Mega-Megalodon/Whale would spawn somewhere on the map (because this species of fish feeds on pirates (It baits them with the treasure inside)) and it would be a water/flesh themed fortress. It would basically be a normal fortress but the catch is that every 30mins-1hr it would change locations on the map BUT ships would be able to hook onto this beast of a fortress mid-travel. Plus any pirates along the way can do the same.