So I touched on the idea that in the earlier builds of the game the voyages you purchased from the various factions had more lore in them. But also I was thinking about the lore in the various emergent encounters such as ship wrecks.
For example: Imagine your exploring an island and find a journal that tells the tale of a ship and a crew. Imagine if you find several journals (again this is not related to the expansions or DLC) and really give the player a sense of this crew and their adventures. Maybe like Flameheart they too turned into Skeletons.
Than imagine you randomly come across their shipwreck to loot. Suddenly that shipwreck isn't loot and supply box with no other purpose. It is now a physical part of the lore and story of that crew. And now imagine when you take on an Order of Souls voyage it is to hunt down that very crew. Now it's not just another grind but actually there is a story behind these skellies.
What if on a voyage you happen to come upon a castaway on one of the smaller islands. And he trades safe passage back to the outpost for his knowledge of some buried treasure.
What about planting some dialog on merchants related to various voyages or shipwrecks. It's about seeding the storied throughout the world for players to come across and discover.