I haven't experienced many dive shops despite being here two years, but that's basically because we've been very happy diving with Ocean Concepts. They're a larger operation, but very professional and friendly. They work mostly out of Waianae harbor on the west side of the island, so even though they will pick up and drop off almost anywhere in town, it's a bit of a drive. The conditions are usually great out there, but from Waikiki it's probably 30-45 minutes. I was certified when we arrived, so I never tried their intro program, but we've picked up a few other courses while we were here and always had good experiences with their instructors.
Best of luck with the choice and hope you enjoy your trip!