Maui has lots of good dive ops and the old "pick a random name out of the yellow pages" approach will work. Many of the dive ops have a particular personality that make them better suited for particular types of divers.
Harbors and Boat Ramps
Lahaina Harbor and Mala Ramp are in West Maui, just a few minutes from the popular Kaanapali resort area. This is the best departure point for going to Lanai. While some operators do run from Maalea or Kihei to Lanai, it's a long boat ride that will seem even longer on the return trip after the tradewinds kick up the seas in late morning. Similarly, Kihei boatramp is the closest to Molokini and driving to there is better than taking the longer boatride from Lahaina to Molokini.
Maalea Harbor is the closest departure point to Molokini for larger boats that don't run out of Kihei boat ramp.
Kihei Boat Ramp is the closest departure point for Molokini. Several 6 passenger and 12 passenger boats depart from the boat ramp.
Dive Operators
It's hard to find a bad operator. The choice of dive op is more a case of finding the one that best suits your personality and dive style. The character of the trips is set by both the crew and also what sort of clientele that dive ops has.
Lahaina Divers, departing from Lahaina harbor, and Maui Dive Shop (check-in at the Kihei outlet store) are the biggest operators, with multiple boats. Lahaina Divers has the biggest boats going to Lanai and are best for those prone to seasickness. Lahaina Divers is used to working with new and occasional divers.
Extended Horizons is a 12 pack out of Mala Ramp. The owner often Captains the boat. They spend a lot of time talking to the divers on the trip over to Lanai in order to assign divers to 2 groups by experience level. My favorite dive op for Lanai.
Hawaiian Rafting is another 12 pack going to Lanai from Mala. The boat is not as nice as Extended Horizons ... a lot bumpier ride, and getting back onboard involves more degearing.
Mike Severns is run by Pauline, a biologist, who often DMs on her 12 passenger boat. Outstanding briefings on the flora and fauna you are likely to see on each dive. Pauline is the person the other dive ops go to with their questions about marine life. In addition to the standard Molokini and S. Maui coral dominated dive sites visited by others, Mike Severns often does the 80' sand and algae dives like the tank and landing craft. If you are a fish nerd, this is definitely your boat. The captain and mate go diving during your SI, so you will have a nice long SI. DMs don't rush you out of the water, and I've done lots of 60+ minute dives with them, both at Molokini and S. Maui. Highly recommended.
Ed Robinson Dive Adventures runs two 12 passenger boats out of Kihei boatramp. They tend towards more aggressive dive profiles than other operators. Their 3 tank dive trip typically starts off with a drop down to 130' to either check out some black coral and a shark condo, or to another spot to see some long finned anthias. I've also hit those same spots a couple times with ERDA on their normal 2 tank trips. As with other 12 px boats, they split into two groups of 6 based on experience level. They also run from Kihei to Lanai a couple times per week, but I prefer to drive to Lahaina and take the shorter ride with Extended Horizons.
ProDiver Maui has a full-sized 34' boat run as a 6 pack. It changed ownership in mid-2004. Under the former owner-operator it was my personal favorite, and I will definitely be checking it out when I head off to Maui in a couple weeks. Lots of repeat, experienced customers. Earliest departure. Often returns as early as 10:30-11AM, which works out well for divers with non-diving spouses.
B&B Scuba runs a 12 passenger jet-boat out of Kihei boat ramp. Although B&B is a favorite of many others on Scubaboard, I found the boat a bit cramped. Some of the DMs were rather inexperienced and also not very knowledgeable about the marine life. Generally departs a while after ProDiver, but it's a tossup as to who gets to Molokini first. Customers were more or less average experience level. Dives tended to be about 45 minutes long
Scuba Shack also runs a a 12 passenger jet-boat similar to B&B. Both Capt Darryl and the owner, Charlie, are interesting characters. I've only taken 2 or 3 trips with Scuba Shack. One of the DMs manhandled a baby whitetip reef shark; and on the trip before, a different DM goosed a banded conger eel to get it to pop up for photos. Due to crowded boat and awkward exit gate, it isn't one of my favorites.
Dive and Sea Maui is a 6 pack owner-operator boat, smaller than ProDiver, running out of Kihei boat ramp. I had a good time on the only trip I've taken with them.
Maui Diamond II runs out of Maalaea Harbor. I've only been on this boat one time, and didn't return after 2 lackluster dives from the same mooring buoy inside the crater with a DM that seemed to be lost. Maui Diamond II is also the boat that left 8 divers in the water for 5 hours after a Molokini dive in Feb '03.
The snorkel excursion boats such as Teralani and the Trilogy boats offer diving on their excursions to Molokni and Lanai. Often, the divers are non-certified divers doing a "discover scuba" dive, so the dive spots are chosen for depth and safety instead of attractiveness. When taking houseguests or family out on these trips, I just snorkel with them rather than going diving.