Your questions are mostly answered by the rules that (ii) a tile can only be placed on a free side of the space the ship is standing (ie, there must be no 'existing' tile there, and (iv) the ship must then be moved on to the circle in the newly placed tile.
What happens if the ship sails off the edge of the board, i.e. the newly placed discovery tile connects to one of the board edge starting spots? Does that players turn end immediately?
The ship cannot sail off the board. If the new tile also permits another sea route, then play could continue, but not if the board-edge circle is all there is.
Also what happens when a new exploring tile meets/intersects with an existing explored tile?
See above - the ship cannot continue on to an already 'existing' tile.
If the next player to go has no "already discovered spaces" to start his turn from, can he choose a new starting spot anywhere along the board edge?
Yes. A player starting his turn can always choose to start from a board-edge circle. I agree the rules don't make this so easy to find. But they do state that at the beginning of a turn the ship is placed by the player on an already discovered space, and the areas where the board-edge circles are referred to as discovered side areas.