Building a navy feels like too much of an exploit since the AI doesn't use naval forces much. They do occasionally build ships, move troops over the water, and build cities on other continents, but these are rare in the first case, and almost never happens in the second in third case. At most a fleet of 3-4 frigates should be enough to act effectively on the seas, without exploiting AI stupidity. Also, naval forces are nice for bombarding, but once again the AI has no idea how to counter them, so use only one or two ships for this, or you'll be exploiting the AI again.
At least I've tested the above on a Small Continents map on King difficulty.