You know... I clearly remember on my first time ever at [BtS] that Justinian came one fine day and declared war on me from his palace at the other end of the ocean. A few turns later, and to my surprise, galleons appeared on my eastern coast pouring knights and musketmen on my territory, while airships bombed all my defensive units. That time I really felt the AI had mounted an excellent naval invasion and felt clearly challenged until I finally had to forfeit the game. It never happened again.
Yes - one was quite wise to either have sentries or be sailing around yourself... I play IV/BTS on archipelago a lot -- always fun to be patrolling around, see a big naval AI stack, then shadow it while sneering at the PC "Now... where do you think YOU'RE going?"
I'll give this to the AI in IV/BTS, too -- there were times when I spotted these armadas, noted it was clearly heading in my direction, rushed over my naval forces -- and it would change course and go after someone else instead.