+1 for Dolphin Diver.
An annoyance of the charters up north is all the boats seem to go to the same spot, as if more divers in one spot enhances the experience and that we needn’t be concerned about scaring the sea life away.
470SAR is cheaper than the current rate down in Jeddah, which has risen to 500 to 700SAR.
The Medina-Yanbu road trip is not impossible, about 2.5 hours. As others have indicated, the other legs are best flown if you don’t live there. I was there for two years and had the resources to haul divers and SCUBA kit for LOBs out of Yanbu and Al Lith (south) so driving all over the west was not a stretch.
If you drive anywhere, pay very close attention to the speed limits. It’s not the police you have to worry about but the speed cameras. The tickets can really complicate a smooth departure. I only had a couple of tickets during my time but knew first hand of others who had problems leaving the country because of unpaid tickets. No fun to be all packed up at the airport and find out you can’t leave because you haven’t paid your speeding tickets.