Hey Victor -
Sounds like a good plan to me - Alona Beach (Balicasag Island) and Apo Island are among the pearls of Visayan divespots! Its easy to get to Alona Beach from Mactan, get a cab to the port of Cebu City and take the Ocean Jet to Tagbilaran on Bohol. On arrival just ask one of the cabs to drive you and your girl to Alona Beach, probably 20 to 30 minute drive. In Alona Beach I like the Alona Tropical, it has good value bungalows, a couple of them almost directly on the beach. And the staff is friendly, the restaurant makes some great spaghetti bolognese, exactly what you need after your night dive! Alona Beach, as the name implies, is a beach with the dive shops, bars and hotels all immediately on the beach - so just scout around when you look for a dive shop. Genesis Divers is usually well spoken of here on the board, I dove w/ Baywatch Divers cause they have a fun young crew and awesomely cute Japanese female scuba instructor
and were a bit cheeper. If your off to Apo Island next you may want to go w/ Sea Explorers, they have a dive shop at El Dorado resort near Dauin (just south of Dumaguete), from which you can dive Apo Island. In 2003 they offered discounts if you made 10 dives with 'em - and you could count the dives made in whatever Sea Explorers diveshop around the Visayas (there's on in Cabilao too, and think in Moalboal as well but not sure). Sea Explorers is in a bungalow part of the Alona Tropical resort. On resorts in Alona: I stayed at the Alona Kew twice and always ended up transferring to the Alona Tropical, the latter is nicer (IMHO) and better value. When diving Balicasag its perfectly okay to dive the same spots for a couple of days, there's a enough to see! And the pygmy seahorses at Arco Point, of course - think we spotted 7 on just a few fans! You will have a great time there.
After Alona Beach track back to Tagbilaran, take the ferry to Dumaguette and a bus or cab to Dauin for one of the resorts: El Dorado or the Atlantis. I stayed at the El Dorado and its a nice and comfortable place. They have the Sea Explorers outfit there, but Atlantis is also a dive resort. Look around what people think / say. El Dorado has a house reef (or better: patch of sand) with lots of cool stuff if you look well. And Atlantis has, i thought, a house reef w/ mandarin fish....look around on the board, there's a lot of info on both. I recall that I found diving at Apo Island nice, but not special - but probably due to the divemaster who was new and got lost in three meters of water...
After Dumaguette its easy to cross back to the southern tip of Cebu and take a bus to Moalboal (or get a boat to Cebu City directly - not sure whether that service exists, you would think so). Which will be a bit of a let down after Alona Beach - same concept but less well executed and where did the beach go? (Apparently it blew away). Anyway - Pescador Island is well worth two days of diving. And Eve's Place in Moalboal was in 2003 very comfi - and next door the diveshop w/ some very skilled divemasters.
From Moalboal to Cebu is two to three hours by bus/cab. (From Cebu its 5 hours to Malapascua...threshers!).
Well hope this provides some reference. Do look around on the board...if you have time, also consider Cabilao (near Tagbilaran) and Southern Leyte (bit further out) and Malapascua. And if you are a surfer....Siargao comes highly recommended! (Tales of tiger sharks are abundant there by the local fishermen....but the only ALU80s available in the area are at a very posh and beautiful resort, out my league :shakehead (for now ;-)).
Envy you going out there w/ your diving girlfriend, take care and enjoy the place!
Happy bubbles :scubadive - Arie.