Hi Cherry,
To get you oriented, Maui is my 2nd choice among the main islands after the Big Island. Who you dive with really depends on where you are staying because Maui is like two islands: south side which has Kehei, Weilea, and Makena - with some good shore diving and located close enough to the Molokini preserve; and the west side, meaning Lahaina, Kaanapali, Kapalua, etc. Ops at the latter can make trips out to to dive such sites as Cathedrals #1 and #2, Monolith, Sergeant Major & Turtle Haven.
Mike Severns dives out of Kehei boat ramp and is the operation that has the greatest knowledge of Molokini - both he and his wife are biologists and have the definitive coffee table book. Out of Lahaina, the Mala Wharf, is Erik Stein's Extended Horizons and they also supply good equipment. Both of these are charters, and do not have stores. Lahaina Divers is a safe operation that caters to the walk-in trade and a good cattle boat op. Day trips to Lanai good, but Molokini Crater way over rated -- it's snorkel & scuba central & shows the wear & tear. Back side can be good, weather permitting, but is for experienced divers only due to depth, current & often rough surface conditions. Ed Robinson's also a very good dive op.
On the north shore of Maui at Nakalele Point (where the lighthouse is) there is a wall which plummets over 120' straight down (might go more but that's as far as I've gone). I admit that it is a very tough climb down and then back up the lava cliffs, and that it is a very physical dive, but the wall is still there for the hardy (mountain-goat types). As to the coral situation, there are two very colorful areas with literally many (perhaps hundreds of) acres within easy shore diving distance. One is right along the road to Lahaina at Olawalu. The other is on the north side about 3 miles past Kapalua. It is a marine preserve called Honolua Bay. Describing shore dives; also purchase the small paperback for about $10, "Divers Guide to Maui."
Eat at Roy's (creative pan-Asian cuisine & not inexpensive), Nicholina's, Sam Choy's, Longhi's (big splurge) & Stella's Blues Cafe (organic).
Best regards.
DocVikingo