We spent March through October 2010 exploring the Sea of Cortez on our sailboat. The diving was not good in the La Paz area until after July, the vis was poor & the big stuff wasn't there yet, the water was too cold & the critters follow the warm water. Once the water warmed up the diving was spectacular, we spent August through October diving all along the Baja side of the Sea of Cortez from La Paz all the way up to Puerto Refugio at the very northern end of Isla Angel de La Guardia and saw amazing wildlife. Counted 5 different kinds of whales, half a dozen kinds of dolphins, manta rays, mobula mantas that actually jump out of the water in formation & do back flips, hammerhead sharks, great fish life, turtles etc. etc.
For divers basing out of shore locations Loreto is an excellent spot, it is central to some great locations, particularly Isla Coronados, & there are a couple of dive ops there. We can't comment on the ops as we are self-contained for diving on our boat & didn't use them, but I'm sure there are some other ScubaBoard contributors that can make recommendations. If you can find an operator further north out of Mulege, used to be one there but his shop closed after hurricane damage & I don't know if it reopened, Santa Rosalia or Bahia de Los Angeles there are some amazing locations. We watched coyotes catch sting rays off the beach for dinner in Animus Slot just around the corner from Bahia de LA, absolutely amazing, have pictures to prove it.
Regarding the poster that said Mexico is completely unsafe we couldn't disagree more. We spent a year in Mexico exploring the Pacific coast from Ensenada, through the Baja & Sea of Cortes, down the mainland side from San Carlos to Mazatlan, Puerto Vallarta, Manzanillo & Las Hadas, Barra de Navidad, Zihuatanejo, Acapulco, Huatulco, and every little village in between, along with multiple inland trips to many villages & cities, Oaxaca is amazing! We never had any problems anywhere we went and never felt unsafe. We have also done numerous trips to the Yucatan, including Cancun, Isla Mujeres, Puerto Morelos, Playa del Carmen, Akumal & Tulum, including a month in that area earlier this year.
Like anywhere else in the world, there are places you should avoid, especially at night, and certain towns or cities to stay away from. This is true in Canada & the U.S. and most countries in the world, have you been to Oakland lately? North American media has done an amazing job of convincing people that Mexico is unsafe, don't believe everything you read or hear, go & see for yourself.
We would recommend going to the Sea of Cortes later in the year, there is some good diving around La Paz but not until the water warms up & clears up, usually around July.