Don't underestimate the shore diving! There is easy access to a number of shore dives in the Kihei area, and if you are willing to drive to Lahaina, some wonderful ones up there. We did Ulua beach as day and night dives, White Rock, and Ahihi beach in the Kihei area. They were all good dives. The day we spent with kidspot, we did the Mala Boat Ramp (one of the best dives of the trip for me), Old Airport, and Honolua Bay.
The shore dives are wonderful because they stay pretty shallow (for us, usually in the 35 foot range) so a tank lasts forever and NDLs are almost irrelevant. There is a ton of sea life to admire, and a dive costs $10 (even less for us, because Peter's folks live there so we got the local resident discount rate).
Comparing the shore diving to the charter diving, I decided that, although we will go out on boats again, I will tilt the balance toward a LOT more shore diving for future trips.
If you are interested in good information on shore diving,
www.shorediving.com has good descriptions of dive sites, including photographs of the entries and parking.