@mrtristifer I wish I'd come across your video sooner. I guess we've all been spoiled from games like assassins creed where you were guided through the controls and where to go to start and prompted at every turn to get through the basics.
Your video does give a good overall guide to the type of missions, but it still misses out important aspects, like the signposts at the outpost telling you where to go to find the different faction members. It could also do with telling the player where on the ship they need to go to in order to select and start a voyage. Then there is the issue with merchant voyages that you need to go back to the merchant to get crates. Once you've done one of these missions its pretty obvious but as a complete newbie it is not only dumb founding but frustrating as well.
You mentioned about joining crews in the middle of the ocean that had no idea where they were going or what they were doing. This is a testament to the rest of the game mechanics that they were able to set sail without any tutorial. It is purely the setting sail with a purpose part that is a problem.