Wow! 3 weeks is a lot.
Local Cabo diving is worth a day (lands end and neptunes finger are OK dives if you get out early, but there is a ton of boat traffic.) Manta or Dive Cabo are good outfits, Sea Creatures is who Nautilus uses. East cape is unremarkable. Gordo banks is a nice pinnacle and you might drop onto large pelagics and the blue diving is a nice change. Two days max and I want out of Cabo!
Heading down to Cabo Pulmo is worth doing, but I would stay there instead of doing a day trip. I think Cabo Pulmo has at least 6-8 good dives (3-4 days) and a chill atmosphere. I like Cabo Pulmo Dive house on the right side of the one street in town. There is nice snorkeling to explore around Cabo Pulmo and at beaches south. Great beach walks and very laid back area. 4 or 5 days and I am ready to move on.
Heading over to La Paz is again 6-8 good dives. (3-4 days). Sea Lions Dive Center is pretty good, but La Paz diving is a bit more expensive due to the longer boat rides to dive sites. Some of these you will likely do on the live aboard. La Paz is a real town and your can organize other excursions. Getting out to the islands is nice, sea lions etc. You are out of season for whale sharks I believe. Hiking in the Valley of Souls is good for variety. A week in La Paz is doable, but it is a small town.
So far we are at two weeks. You might head up to Loreto for a week. Bus ride from La Paz of Loreto is 5 hours and Loreto has again 6-8 good dives. Dolphin Dive or Blue Nation. There are a number of sites closer in to the marina, but a lot of good dives out by Isla Coronado or Isla Carmen. (Again you will hit some of these on the live aboard) A last week in Loreto and then a bus back to Cabo for the live aboard.
For Transport: (No Car Rental)
1. Fly into San Jose Del Cabo.
2. Take a shared ride van to Cabo San Lucas stay close enough to the marina
3. Arrange a private transport to Cabo Pulmo (work with the dive center in Cabo Pulmo for this) Small town, everywhere is walking distance to the dive shops.
4. Arrange with the Cabo Pulmo Dive center to get a ride to Buena Vista so you can catch the bus to La Paz (about 2.5 hours). (Or arrange a ride to La Paz) La Paz is a small town and taxis get you around.
5. Bus from La Paz to Loreto is direct about 5 hours. Loreto is a medium town and taxis get you around.
6. Aguila Bus from Loreto to Cabo is about 9 hours, end up at SeaCreatures OR arrange with Nautilus to meet them in Loreto and save your self the 2.5 hour bus ride from Cabo to Loreto. (When I took the Belle Amie it was out of La Paz and you jumped on the bus first thing, Check with Nautilus on this)
I am headed down next week to catch a liveaboard, but I am just flying in, and then flying out.