Okay, so: update.
Haven't gotten onto the details, yet, but I've had some progress. After much thought, I'm going to make mithril the most important metal that exists in the setting, for quite a few reasons.
The major source of mithril is the long bombardment from a ring of mithril orbs (read: asteroids) that the Church calls "God's Halo"; these orbs circle the planet in that configuration, and, occasionally, fall to the planet below. They believe that the metal is sacred because of its magical potency and power; this means that all spellcasters need and use mithril to perform spells, modifying spell components a little bit (but not much, since most of those are handwaved). This includes clerics, druids, sorcerers, warlocks, and wizards, and the half-casters. Over the course of millennia, mithril has fallen from the sky, been buried in the ground from the resulting crashes, earthquakes, volcanoes, etc; so, this mined mithril is not as pure, and therefore not as potent. The most potent, however, is that which has recently fallen--its power thrums in the air, tingles your skin, and is the most sought after, by almost everyone.
On the other side of the world, there are several governments that control mithril; it forms the basis of their economies, and religious doctrines. Each nation has similar religious views, with minor (and sometimes major) differences; compare to modern time's abrahamic faiths for the same basic idea. In addition, mithril, through it's mystical properties, can change a being in different ways, imparting grace, luck, or magical ability; this is the formation of spellcasters and magic, and has been thus for centuries upon centuries. Because of its properties, though, mithril can occasionally change a person themself, making them different from other humans. These 'others' have become two different races, the mithrins, and the mithlings. The mithrins are terrifyingly beautiful, capable of great deeds almost from birth, while still maintaining a link to the rest of humanity; mithrins use the halfelf stats. The mithlings, on the other hand, are blessed by fate itself, it seems, light of foot and lucky beyond chance; they use the halfling stats, with added darkvision, most likely. The only other 'race' is humans; I have yet to decide whether or not there will be different types of humans, or just the same race; I'm edging toward not.
Mithrins and mithlings, however, are treated as second class citizens, at best; at worst, they are slaves--or dead. The churches view those 'tainted' by mithril has cursed by god, because their ancestors stole some of god's grace, and it must be returned to Him--usually by killing them in the Trial. Often, however, they are captured, forced into slavery, and put to work in mines for mithril, as their ability to see in the dark makes them good at that sort of work, and they can serve the God they profane, until such time as they are cleansed (i.e. they die of old age).
Outside the empires, such as in the area the group will be adventuring in, the mithrins and mithlings (derogatory: mitzies), are treated little better, but at least they aren't taken on sight, save in the colonial cities of the empires. In the pirate colonies and amongst the pirate kings, they are treated as people, and many of those who sail the pirate flag are one of the "tainted".
Big events that will occur (these will happen mostly in this order, at least at this early stage):
1. The Pirate King they serve (whichever they choose), has a subordinate that does not like how successful the party is, and must somehow remove them from the picture, so he can discredit the current King and take his place. Haven't figured out how he's going to do that, yet, however (could use some help with this idea, as it happens fairly early on).
2. Death of the Emperor; his son takes over, and has his protege lead a small fleet of the best naval vessels to waylay pirates, and end their depredations. The group will run afoul of him eventually, and will have to battle him, as his orders are to take no quarter from those who sail under a pirate flag.
3. An undead lich's cult uses necromantic magic to take control of a pirate king's fleet and the pirate king (an opposing, or at least not actively hostile one to the one that the party join), and uses it to gather Mithril, as much as possible; the cult needs it to resurrect their "God", the undead lich. They take other pirates for their loads, and will probably sack the party's pirate king headquarters, killing the pirate king, so they can eventually, hopefully, take command. How I'm going to get them to that point is beyond me just yet. They should eventually take the fight to the controlled pirates, taking them down (hopefully) and hopefully find out about the cult; they can tackle a cultist headquarter somewhere, and then find a clue to the lich's secret headquarters, so they can destroy his phylactery in an enormous necropolis.
During this will be the sandbox-y parts, I think. I had the idea of using the four "levels" of play (1-5, 6-10, 11-15, and 16-20) as the four random tables for what they encounter in their sandbox, so as they get more money and experience, the average of the tables gets more difficult. Pirate fights, fights against the navy's of the world, encounters with sea monsters, finding treasure maps and hunting down what they say, etc, will populate the tables.
I am still unsold on using Gold-for-XP, however. As good as it would be for this game, especially, I am not sure how likely it will actually work. I might do something similar, but they're used to getting xp for monsters, so I'd not be sure of how to get to use both. Don't want them to progress that fast. Maybe allow them to spend money on XP, so they can choose to spend it on weapons, magic items, or XP, but not XP + items? Dunno.
EDIT: I think I'll make the seven Pirate Kings (Pirate Lords? Not sure which I like better.) actual organizations, and, if they can gain renown, the amount that they have to pay the Pirate King from their booty (lol) actually goes down, because their rank goes up. Gives them a reason to actually do some things for the King to raise their Renown, and also gives a trackable way to show when the King's subordinate gets uppity and decides to do something about the party.
Also, do you guys think I need Backgrounds?
Ideas:
1. Pirate Crewman - Served on pirate crews before, know where to find other crewman and/or other ships to crew on. Don't make much as a crewman, but its better than nothing. Now you want to branch off with your own ship with the party.
2. Heathen Devil Worshiper - Similar to Acolyte? You worship one of the gods of the islands, or similar deities, etc, something off the beaten path of the big three religions.
3. Mage of a School - You belong to one of the schools of mages; you know the proper marks to find safehouses, maybe, and maybe advantage on fencing magic items rolls?
EDIT EDIT: Maybe I can think of a way to work in Necromancy in general, and the lich in particular, to the early adventures, so the theme will be present, but mostly subliminal--would that be the appropriate word? Not sure.
I'm also going to need more sea monsters. Lots more sea monsters.
EDIT EDIT EDIT: Actually, including necromancy/lich wouldn't be hard, because that could be ruins.
A large deposit of mithril destroyed his continent during the ages long before the current era when it fell to the sky; he was slain, but his phylactery survived, and his cult are trying to resurrect him by loading up on the mithril because of its power. So, a lot of the ruins in the area could be parts of that sunk nation, which the lich will attempt to raise from the sea floor should he be raised from the dead.