The chance of being recognized at sea depends on:
. Difficulty level
. Luck (=sneak) skill
. Fame level
. Distance to other ship
At a great distance, you're not likely to be recognized, but the closer you come, the higher the chance to be recognized.
I take it your fame is still low (only just started a new game, right?), so you will need to build up your luck skill.
As Malcolm Hatcher will tell you during the Standard storyline tutorial:
Luck will improve when you play card games in taverns. Also, you'll make it better when finishing quests and still remaining alive. Or, finally, by talking with encountered people; but beware, captain, when your Luck is low, some of them will probably try to steal your belongings.
On land, there is no such recognition modification.
There IS, however, this dialog that can be triggered by talking to random town folks:
"Hmm.. I have seen you before.. during a ship skirmish some time ago, on a quarterdeck, I think... Yes, and with a black flag.... HEY, you are the devious bastard who sailed close to our ship and then suddenly hoisted the Jolly Roger !!! ALARM! A pirate in disguise! ",
" Should have killed ALL witnesses of my piratical past..",
This dialog will only be triggered if you actually deliberately hoisted a pirate flag at sea.
How to prevent getting this dialog? Well, don't hoist a pirate flag! If you want to attack friendly ships at sea
without getting a reputation hit, let them know you want to attack them by hoisting the flag of a nation that is enemy to them.
You will not be recognized for this (though maybe we should code it in so that you can).
Alternatively, try to avoid conversations with random town folks (generally recognisable because they all carry weapons).
However, sometimes they will address you when you come close, so you probably won't be able to avoid this forever.
Wearing different clothes has no impact on this even in the slightest.