A few more than I intended... and some are not well suited as "random" encounters..., but IMO these are useful or cool...
A large, clumsy boat is discovered adrift. Two animals and monsters of various types are starving onboard. They crew is discovered slain.
A leak threatens the ship. (Fire was also a threat on ancient ships.)
A group of humanoids appears to be sunbathing on a distant beach. As the PC's approach, it becomes more and more clear that these are middle-aged orcish females. Nasty handouts pulled from the Internet and Photoshopped green could be fun. Bogus sanity checks?
Bloated corpses floating in the water...
A friendly ship is found at anchor having difficulty with a deep-water salvage of a treasure ship.
A typhoon threatens as the crew races to claim the treasure/catch/strait before it hits.
Playful seagulls/dolphins/mermaids have been following the ship for days.
Each morning the deck is completely clean... the ship has a family of brownies.
A passing gnomish airship taunt the shipboard PC's as they fly over. One of the jabs bears further investigation... but how to get on the airship?
A floating island (in the air) starts following the ship.
A passing ship demands they escort a small band of chained pirates to the PC's destination port for trial... as is the marine law of free peoples. They may not refuse, but the pirate may not be what they seem... or they just may speak Pepe Le Pew French incessantly.
A talking sea creature speaks of a great sea turtle sage that has lived since 'the oceans were new.'
A crew of shifty looking fellows are found salvaging a large ship with shallow skiffs. The ship appears to have run aground in recent days.
A wind blows from an unexpected direction. Sailors know that some have sailed to a remote island on this wind before to great riches.
A sea culture surfaces with an offer of trade for exotic underwater riches. In addition to wishing for bronze, paper, wine and glassware, the culture may barter for services.
Pearl diving... monstrous oysters. Diplomacy... with the herring high council to improve fishing... perhaps as they betray the shad.
A dryad's tree was used for the mast. Undetected, she is secretly killing the crew at night as she hides in her slowly dying sanctuary.
Hurricane blows ship through a time or dimensional gate. Land of the Lost or other impossible continuity adventure awaits.
Were-parrots. They are evil spellcasting thieves. Polly wanna be captain.
A random PC becomes increasingly claustrophobic and anxious, feeling trapped on the ship. Normal reaction or sorcerous influence?
A narrow strait demands the ship thread the needle between a whirlpool and a siren. Flip a coin to see which direction the ship veers as it makes a small navigation error.
Three Capricorni approach to PC's ship needing help to pass through the coral archway guarded by the marine troll.
Large wicker and pitch barges (30' diameter) are found anchored near the shore. They are piled high with seaweed/jellyfish/shiny shells/swamp grasses/uprooted trees/giant sturgeon eggs. In 2 hours the knas, a massive underwater humanoid race from Mystara, return to drag their booty back to sea.
Nixies on the beach merrily racing along the sand riding 40 pound sand pipers. Fierce betting.
Take a land monster and convert it to a rare marine version. Sea basilisk? Water camel herd? Floating green slime?
In the shallow white sands of the bay, it appears that streaks of black sands run through it. Like a crop circle, it becomes a clue if PC's fly up at least 200 feet to discern the image.
A great resting flock of aerial creature migrating across an ocean is disturbed as the ship sails into their midst.
A valuable 'battery eel' school is discovered. Wizards and trap-makers will pay top coin for captured specimens.
Under curse, the rigging of the ship has become sentient. Ropes need to be persuaded to allow sailors to knot them. Another curse... PC's must only communicate with "Arrrgggs."
The xorn have been slowly filling an atoll with earth to reclaim it from the sea. The Crab People approach to PC's for their help promising gemstones.
Stirges dive from the cliff face at passing ships.
A ship piled high with straw appears to be sailing slowly toward the PC's. How long will it take before the PC's realize it is a fire ship crewed with zombies?
A glowing ladder appears from the moon. A legend is that on certain moons, you can walk across the moonlit ocean and up the ladder to the secret civilization that governs the moon with an iron fist. The mice-people. (Use Reaper Mouslings.)
The ship must be ported 15 miles across the shallow swamps in the middle of the ocean. As all know, there is a great marine swamp too vast to sailed around, but that with the help of the sea turtles, ships can be ported across. Bartering with turtles in never easy as they want so little.
Navigation error. Food or water low. Scurvy. Sickness on board. Low morale. Sunburns. Billowing mists. Lightning strike. Man overboard.
In this part of the world, ships often anchor for a few days near a great coral reef to dive for semi-precious shells and to hunt exotic marine life for sale to improve margins.
A floating chest. With only nominal items of value, a shipping manifest has an intriguing entry.
From a distance, the PC's observe a great armada sailing to war... perhaps against their homeland. Can they get there first?
Skinny-dipping Fire Giant maidens.
Unexpected flotsam. A carved, wooden door with a mysterious rune and an unknown creature. An uncharted nearby island?
Angry fishermen wave fists from across the waves as the PC's ship fouls their nets or crab pots. If the PC's can rectify their error, a clue is provided.
A bonfire is burning on the coast at night as if to attract passing ships. Pirates... trade opportunity... rescue... etc.
The anchor is lost at sea and needs recovery by divers and/or magic. Of course a sea monster lies in wait. If not recovered, the ship may run aground in the upcoming shoals.
Part of the deck is made from a talking tree. He is very chatty and knowledgeable about his home forest 100's of leagues away.
Ship entangled by the webbing of giant sea spiders. In 2 turns, they will begin boarding.
An arm keeps rising from the water holding a sword. It disappears for 10 hours each time the PC's get close.
Crew struggling with the ballast causing the ship to list heavily. Combat on this trip may be -1 to-hit and possible tumbles overboard as the deck is badly askew.
The ship sails into a low-hanging invisible floating air island and ravages the sails and upper deck. The ship is beached against the underside of the slowly sinking island. Climbing onto the island to make repairs becomes necessary. Why is island so low? (Obviously, invisible floating islands can be seen from above.)
Two of the NPC naval officers hate one another and are dragging others into their escalating, onboard feud.
Ship at anchor near coast with only a small crew. The rest are on the coast foraging for water and supplies.
As all know, a placid sea on a windless night always stands a chance to open a portal to the Nightmare Dimension. The reflected ship pulled into the Prime Plane is the opposite of the PC's... very Star Trek but with zombies.
Exorbitant port fee from a clearly corrupt harbor master.
When the PC's near their destination, they pass a port city that has been destroyed when the volcano over the town exploded... 3 years ago. Many of the stone buildings in town were only half-submerged by lava as it flowed into the harbor. Some ships survived, but some burned. The town is overrun with marine undead.
A badly sunburned ogre with a fishing pole is discovered sleeping in a crude, floating chair within a few miles of the coast. He will awake with a hangover. While not a threat, he may have information.
Discontent festers on the ship as the officers live on fine victuals while the crew suffers. The officers will resent the PC's unless they rectify the situation in the most diplomatic of manners.
Barnacles need scrapping despite being at sea. Failing to do so may slow the ship such that supplies exhaust. Pick-a-monster.
As the PC's ship flounders, they must board a passing boat of amorous sea-elves on a pleasure cruise to a fantastical island able to source the parts needed for the PC's ship. After a sanitized love affair and a caper, the ship enters the port of the gnomes, "De boat! De' boat!" Gnomish illusionists can grant most any fantasy, but there may be a twist with an object lesson.
A friendly NPC crewman is falsely accused of a flogging offense. The captain may plot revenge (stranding?) if his discipline is thwarted. The sailor may die if the punishment is administered.
A large, crude raft of primitive, non-threatening humanoids is found deep at sea. They are well stocked and know of a far-distance shore from legend.
A pirates body is found on a small dingy at sea. Around his neck is an engraved copper plaque... a letter of marque from the pirate king to allow the wearer to pass unmolested about his business.
Low-hanging clouds hang into the sea. The PC's see a castle 'inland' on the cloud. The substantial cloud could be explored.
The old Expert module War Rafts of Kron is an open-sea adventure. Also the Mystara supplement "The Sea Peoples" is rich in ideas.
A great sea beast's corpse is found floating or beached. The markings suggest a predator of unimaginable size.
Many of the galley's oars are crushed in a freak brush with a large whale. The ship must limp back to port are greatly reduced speed.
On shore, humanoids are seen tied to stakes as if an offering to the sea.
Due to a design flaw, the ships rigging keeps fouling. Navigation and maneuver will suffer until it is repaired in dry dock.
Two winged figures leap from a high cliff. One glides toward land while the other rises up and tumbles into the sea.
Poor ship discipline causes drunken belligerence, possible mis-navigation and even the lookout missing land as the ship sails by.
On a low coastal island, a humanoid work crew appears to be stacking shells in a large circle... the foundation of a new nautical city.
A distress cog is found adrift. Inside the gutted ship is an abandoned giant-baby.
Friendly authorities board the ship in a routine manner, but the ship logs prove problematic. The cargo is seized.
The crew demands shore leave. Very rough seas. Superstitious sailors have seen an ill portent. Night watch. Will-o-wisps in the Triangle of Lost Ships.
Underwater kamikaze kobolds riding giant flying fish attack from the depths.
Awful sea sickness for one random PC. Maggot-infested foods. Filthy conditions on the ship has attracted swarms of insects... for ships that must hug the coast.
An illusionist is creating powerful illusionary lighthouses along a contorted coastline and wreaking havoc with shipping. His goons (crab-riding grippli?) are collecting booty along the beaches.
A young crewman is believed by the crew to be divinely blessed. He fosters jealousy and fear despite his pure heart.
A crazed necromancer is found near death adrift on a sheet of ice. He keeps ranting something about his monstrous abomination that must be stopped before it kills again. And someone named 'Elizabeth.'
A florescent mass of jellyfish arise from the depths one moonless night. An evil other-wordly monster of your choice may accompany them or just use it to enhance the atmosphere.
A PC is found unconscious... apparently from an unsecured yardarm. An accident or foul play? The PC will recover in a few days.
Treacherous shoals and currents. Rip tides. Red tides. Crew dysentery. A floating patch of dead fish.
A major transoceanic current proves to have shifted while the ship is in the middle of a long voyage. A choice of destination must be made... follow to current to parts unknown of potentially die before reaching the original destination without the current's help.
The world really is flat.