For a lower mid-level party (Level 6-8) using Pathfinder/D&D 3.5 OGL rules. This encounter is meant to be resolved through combat, for there is no room for negotiations where the Mad Hag is concerned…
Alter this encounter as you see fit, masterful DM!
The player characters are aboard a ship sailing through uncharted waters (or perhaps it is charted but known to be dangerous). It’s well past midnight and a storm fast approaches (Nature/Survival DC 20: the storm is brewing at an unnatural rate, possibly summoned).
All hands on deck!:
Several cries are heard as crewmen are pulled overboard by nets. Sahuagin armed with electrically charged tridents clamber aboard the ship, attacking the nearest shipmates (use an appropriate number of sahuagin based on the party size and the experience of the ship’s crew; send several waves if it seems too easy).
By round two the storm intensifies making it hard to keep your footing (Balance DC 10 or fall prone) (the sahuagin are not hindered by this) and perception is reduced (-20 on all Perception checks; visibility reduced to 25ft for humans). Shouting is barely loud enough to communicate with allies.
By round three, bolts of lightning begin striking the deck (arcing to 1d3 creatures within a 10-foot radius, sahuagin immune).
Like a Boss:
On round five (or whenever you feel it is appropriate), the source of the storm-calling is revealed. A seaweed-covered hag hovers above the ship, cackling madly, sending another bolt of lightning blasting forth from her fingertips to hit another shipmate (use the stats for a sea-hag plus a lightning ability and levitate) (now is the time to use her Horrific Appearance supernatural ability) (she does not fight to the death, and flees when death seems imminent).
If the battle is won, the storm quickly subsides, and the weather returns to it’s previous state.
In the morning, several other ships are found floating aimlessly, rigging destroyed and decks littered with corpses scorched by lightning (insert adventure hook).