Oregondak,
You have the right idea to ask for recommended guides. They are not all the same. If you want to fish from Maui make sure you go on a day long trip, not a half day. We made that mistake, was more of a whale watching trip than fishing. I found out later that you need to cruise further out to get to the better fishing & deeper waters (although some fish are caught close in).
The best fishing is off the coast of Kona, Hawaii. I'm not sure if its worth flying to Kona from Maui for a day or not but it may be. I fish from Oahu once a year with Local Hawaii friends but havent caught a Marlin yet! Usually off season, Feb and March when we go. I really want to fish Kona in the summer months one of these years.
Good luck, -Steve