The ship mechanic is one of the 'broken' mechanics in Civ III. Not broken bad but broken good.
I think the devs wanted you to explore the world via ships right from the get-go (which you can with Seafaring Civs), but later realised that the new Culture function would hinder this to an impossible degree - especially applying any sense of reality to nations having cultural dominance over waters they don't even have any boats for.
For the most part of the early game you can enter foreign waters and be met with the following message the next turn: "Please withdraw your troops" (but not the automatic removal one) to which you reply, "yeah, ok", but then proceed to carry on sailing round their coastline.
None of them will object or consider less of you because of this. At some point, I'm not sure when, the 'normal' mechanic will resurface and it will be better to sail round than through their waters. But at the early stages I have no doubt that they tweaked the Diplomatic mechanic so that exploration can continue unaffected by Culture.
The only times I've noticed them get 'grumpy' is when the route leads directly to a new island that the AI Civ is also competing for, at which point you may get the occasional "please move automatically" message.