If you’re looking to get a good cat sail in on your vacation I HIGHLY recommend booking a Molokini snorkeling and performance sail trip with Paragon sailing charters. Unlike all the other large cats that leave out of Ma'alaea harbor these guys actually sail while the others just motor. On our way back we hit 18 kts with the windward rudder just skimming the water!! In fact the captain said when they hit their top speed of 30.1 kts a few weeks back he had the hull flying, this boat moves you won’t be disappointed.
Check them out:
http://www.sailmaui.com/index.html
Also pick up Maui Reveled, it's a great travel guide for the island.
Kevin