[Chazar]

Neighborship of provinces in Dom2 is regardless of terrain, and flying only respects neighborship, so yes, you should be able to leave your island with flying boots.

However, a sea province always restricts strat-move to one, including flyers: Thus if you are submerged, flying boot will not give an advantage to you strategical movement.

EDIT: I seem to be wrong here: Flying over water does not work even with water breathing flyers...