I once read somewhere how someone described a method to begin a sandbox game as "dropping the players off at the rail station". When you start a new campaign, the players may not know anything about the world except what information you wrote for them and they did not read. Even if it's set in an established world, the players don't know yet who the useful NPCs are that are worth talking to and what nearby locations are suitable and interesting to be explored at this point in their characters' careers. And most importantly, they don't know yet who their characters are. Some players might have written a backstory, but they usually wrote that without knowing much about the world and knowing anything about the other characters in the party.

These are all important things that players need to take their own initiative and start doing things in the sandbox world. And they are also things that become much more apparent once they have played together for two or three sessions. Some ideas they had for characters get dropped unconsciously because they realize it conflicts with the rest of the party and most people with basic human skills instinctively try to avoid doing such things. So you begin the campaign with a straightforward quest. In this case Against the Cult of the Reptile God. "Here is a town, some people you know here have gone missing, and you're trying to find them." This is infinitely better than "You're all sitting in a tavern, you can talk to each other if you like."

Despite the expression "rail station", this first adventure does not have to be a railroad. In the case of this campaign, the players know they need to get from the mainland to the Isle of Dread, but in most sandbox game the starting town can be located inside the sandbox. The starting quest can end in completely unexpected ways because the players come up with crazy ideas, or they can even just abandon it when something else catches their attention. The goal of the starting quest is not to finish the quest, but just give the players something to do until they start having their own goals. When they have found something they want to do, it has served its purpose.

Against the Cult of the Reptile God was a pretty straightforward affair, though the way this adventure is designed the initial sessions inside the town can play out in all numbers of completely unexpected ways. The dungeon will end with the cult leader fighting to the death, but trapping all the enchanted thralls in their sleeping rooms was entirely the idea of the players.

Now Tual has turned out to be a much more open environment, but I still gave the players their main goals: Free the navigator from prison, get the maps from Kamar, and get the Magic Conch from Perang. Only getting the maps or the navigator would have been enough to reach the Isle of Dread. I always assumed the players would try getting all three things, and I believe the players think they are supposed to. But they could also just take one and leave the Magic Conch entirely. That would also work. The Pirate Queen wanting the players to kill Kamar was intended as a backup in case the players screw up in the prison and get themselves captured. That they would go talk to her to negotiate for the navigator was a possibility I had considered, but I didn't have anything planned for that. Starting a tavern brawl and drawing the pirates away from their ship with Alamar's illusion ability was completely unexpected. As was torching the ship.
Tual does not really qualify as a sandbox, but it's certainly a small open world.

When they reach the Isle of Dread, I am actually working hard already to get the players waned from the idea that they have to find and defeat the masters of the Reptile Cult. Their main priority seems to be that they want to rescue the slaves, so I will make this goal very easy to complete. I could take some of those slaves and put them right in the throne room of the Big Bad Evil, but then the whole campaign would probably end up the players trying to finish the starting quest. Similarly, the masters are working on something, but it's nothing time sensitive that would be a disaster if the players don't stop it. Otherwise they will once again head straight for the throne room. In hindsight, having a high ranking servant of the masters in the first dungeon was not a good idea. It would have been better if the naga only have a small base on the beach of the Isle of Dread and are basically wiped out when the players arrive to rescue the slaves. And then the big bads on the island would be a completely different group. But I guess we'll see how all this plays out in the end.

Regarding rules, I found D&D 5th edition quite a joy to run so far. Being mostly a 3rd Edition and Pathfinder player and GM and really not fond of that system, I found 5th edition to be much more simple to run and especially prepare. Though I think the main draw for me are the Warlock class and the Cleric domains. They both have a style that really calls to my kind of fantasy.
For all the exploration and travel stuff, I am pretty much completely throwing out what optional suggestions 5th edition has and almost straight up use the little 1981 Expert Rules. That's the way exploration and travel in D&D were supposed to be. It's a small book with relatively simple rules, and when you read it suddenly everything makes sense about encumbrance, random encounters, morale, and hireling loyalty. Later edition tried to have encumbrance as some addon that no longer served a purpose, and had random encounters without understanding what they are meant to do. I really can't recommend the Expert Rules enough. All these systems that are not about combat are still great and fit together with other D&D editions with very little issue. The only thing I feel is really important to remember is that this whole interdependent systems of multiple mechanics only works when used together as a whole, and it only works if experience point from fighting enemies is only marginal. If fighting is the main source of combat, then random encounters are not an obstacle but a present of easy XP. Even better to go with XP for hauling home treasure, because then encumbrance and resource management really becomes a thing.