I'd dive Maui and Kona. Lots of other interesting non-dive things to do on Oahu.
All the Kona boats are based in a harbor just north of town - nothing nearby. Most shops have an office in town, you check in once then meet the boat daily. We liked Kona Diving Company - they're in an industrial mall just east of town - so are two other shops. (Big Issland and I forget the other) The reason for Kona is the Manta Night dive - it regularly makes the top 50 dives in the world lists. Also south of Kona there's a decent chance spinner dolphins will be your buddies - hundreds of them. There's a few decent shore dives also. 45 mins,. north is Waikoloa - there's 2 boat operators there if you're staying in that area.
Maui has a lot of shore diving options all along the west coast. Plus you can dive 3 other islands, boats based in Kihei go over to Molokini, boats from Lahaina generally to Lanai. The Molokini Backwall is a good dive and the West Lanai drift dives are an e-ticket ride. Once a week Lahaina Divers takes a boat to Molokai to blue water dive with hammerheads - it's seasonal so check with them. Also if you're staying in that area - Kaanapali or Lahaina are very touristy - once every couple days Lahaina Divers also does Molokini. No south Maui boats go to Lanai. Not that it isn't on all islands but Maui Scooter Divers offers rides out to Umekahame - often there's Manta's there during the day. Robinson''s also goes there.
It's about a 45min. drive between Lahaina and Kihei and even at 5am there's traffic - resort workers. The Kihei boats all leave as close to 6am as possible to get back b4 the tradewinds pickup - they're smaller as they launch from the ramp.
My list of operators - although there's many others.
Ed Robinson's - offers more advanced dives
Mike Severns - naturalists on board
B&B Scuba - just nice people. Also a fill station for exotic gases.
Lahaina Divers - two big Newton dive boats but smaller tanks.
Extended Horizons - one smaller boat but a good crew. They also do escorted shore diving - if you plan todive Mala Pier - they're nearby.
In south Maui Doug at Shaka Divers has the dive bus and will meet you at sites. Maui Dreams Dive Co. is the other shore dive operation in Kihei.
Personally we like staying in condos in Wailea although the Kihei boat ramp is about 10mins. north. Most of the Wailea beaches are also good shore dives, we like Wailea Beach - it's very interesting off the south point. A friend told me Polo Beach is better.
a little dated but some good info/pictures -
Scuba Shore Diving Region: Hawaiian Islands
hth
