I wrote up a naval encounter generator for an upcoming Mongoose book (book of the Sea). Let's put it to work:
1. The PCs' ship encounters a huge merchant vessel, with representatives of a neutral good merchant's guild on board. However, one of the merchants is Neutral Evil - he has bargained with a demon. The merchant ship hails the PCs, and asks them to drop off a sealed letter at the guildhall in the port the PCs are heading towards. This letter is marked with the seal of the merchant's guild, but actually contains instructions to a demonologist ally of the evil merchant. If the PCs break the seal and read the letter, they can uncover the demonic plot and possibly win the favour of the guild.
2. The PCs come across a damaged and slowly sinking ship. The only person on board is a cleric. His only cargo is an idol, retrieved by a church-sponsored adventuring party. He demands that the PCs bring him and the idol on board, so he can travel with them to the port city, where he will obtain another ship to bring the idol to his ultimate destination.
When the crew of the PCs' ship bring the idol on board, though, they recognise it. It's a relic of the locathah, something that belongs on the bottom of the sea. The cleric's ship was damaged by a storm sent by the locathah druids, trying to retrieve their treasure. Do the PCs help the cleric, or listen to the fears and superstitions of their crew and dump the icon overboard?
3. The PCs' ship passes a tiny island. An agent of the crown or whatever local government the PCs are loyal to hails them from the shore. He's been assigned to watch ships passing the island, which is on a major shipping route. A few hours ago, he saw a warship flying the flag of a rival nation sailing towards a port. The port must be warned and the warship stopped.
The warship is actually just testing the resolve and the defences of the crown - but if the PCs help out and are too trigger-happy, they could spark off a war.
One more for the sea...
4.An elemental storm. Bah, that's just freaky weather.
5. A merrow starts stalking the PCs ship - it climbs on board during the night, gobbles up a sailor, then slips back underwater. The merrow is very agile and strong. To catch it, the characters will either have to fight it on its own territory, or take a night watch themselves and try to kill a monster that clambers up the side of the ship swiftly, drags one of them overboard, then slips back into the black waters....