Keep in mind that you do not have to actually sail to each port. As long as your boat is on the same "server" as the fishmonger, you can recall to the town dock and complete your quest and get a new one then recall back to your boat. The Server Map located
here should help.
I used to hang out just off of the nw corner of Buc's Den. From there I could recall to Brit - or sail across the server line to the south and recall to Skara, Trinsic, or Jhelom - or I could sail east across the server line and recall to Vesper. It is also not too far from the Serpent's Pillar to get to Papau. This only leaves Moonglow and the Fish-Dock that really require substantial sailing.
Hope that helps!