There should be a few monsters in the sea and when ships kill them everyone on the boat gets some experience for it. (Like a party)
They should be kinda rare though. It'd suck to run into one EVERY TIME you want to go somwhere, you can either run away or kill it like I said earlier.
There could be enemies like giant squid, etc. Opinions?