Perhaps if the ship is becalmed or otherwise in an unfortunate scenario, the crew begin to blame the PCs. You had mentioned that the god of storms is upset with some of the party. Perhaps if the ship has been stuck without a wind for a few days the crew begins to grumble about the party. Slowly, grumbling turns to outright hostility until a sizable portion of the crew is convinced that if they just toss the offending PC overboard all their problems will be solved since the storm god will be appeased.
Certainly the crew could become disillusioned with the PC's setting the ship's agenda, and I plan on doing something along these lines. But I'm hoping for more subtle suggestions for scenes.
For one thing, the PC in question has a +16 diplomacy bonus and frankly, respecting my rules/rulings means that she's a really persuasive person that most people tend to respect and even like and admire. She's about as persuasive as the most persuasive real world examples. This sort of scene might have been more tense for some of the less likeable PC's that have been in the campaign, but right now there is no outright unlikeable character in the group. She by the rules makes friends pretty easily. With a +16 diplomacy bonus, she can reasonably persuade ordinary people to risk their lives on her behalf - she can and has convinced a member of the city guard to not only drop charges on another PC, but to make atonement by giving a gift to the temple for even discomforting her. As long as she doesn't do things that overtly cause people to dislike her - and keep in mind she's the ship's surgeon, a master physician, an ordained priestess of the Sun goddess rumored within her own temple to be a living Saint, and free in using her healing magic to protect normal persons - it's hard for me to see her actually running afoul of a large group. I mean, think about it, if you knew someone who was rumored to be friends with a deity and whom you actually knew capable of summoning rays of fire from heaven, turning steel red hot, and healing mortal wounds and other feats of power, would you dare lay hands on her? Doesn't do much good to appease the Storm Lord and then cheese off the Goddess of the Sun. So while there will probably be grumbling, any threats of this sort will probably come from disgruntled individuals rather than the crew as a whole, and will probably involve actions other than open mutiny.
I'm just not quite certain what. The most likely scenario for a single threat is the Nuatians have put a Malenti spy into the crew (think, 'The Shadow over Innsmouth'). So we could have a variety of assassination/sabotage attempts. Any crew with lingering feelings that Nuati needs to be appeased may try to go over the captain's head and offer sacrifices aboard the boat, which probably has reverse of the intended effect - so there might be a social challenge to dealing with the fact that there is a small group sailors performing occult rites that are actually giving Nuati additional power and influence in the situation. Cleansing the ship of idols to Nuati might grant a small advantage, but THAT could cause grumbling if not handled well (ei, voluntarily) because there is a strong social custom that you can privately worship whoever you like and even the Captain might balk at tossing out the personal effects of a sailor.
Hmmm... ok, so one of the things I'm thinking about doing is having a 'skill challenge' like scene with an occult hurricane, and things like this - whether the spy has been found before this, whether the whole ship has been convinced to give up worship of nuati, could be modifiers on the skill checks to determine the outcome of the storm.
So, ideas for scenes involving petty revenge or attempts to humiliate the priestess? Direct and open conflict with the priestess is probably out of the question, but how would you go about trying to socially undermine her in a way that doesn't get you flogged (or if it gets you flogged, causes the crew to view the punishment as unjust)? If you can open her up to mockery or disrepute, then maybe you can turn the crew against her.