To be quite honest, I would pick the show and menu format that you like the best. There may be some differentiation between food quality, but not enough to matter much. Chefs can have off nights - Lahaina Luau has them, as well as the next luau place. The chef at Lahaina Luau is well known and highly regarded locally. Plus, they've won some awards at Taste of Lahaina, etc. I've heard good things at Lele, Marriott, Hyatt. Everyone has their own favorite. Also, remember that local style food like poke (the raw fish) can be an acquired taste and poi :crazy2. I prefer some of the Asian/Fusion type food - like you would get at Roys and Sansei. There's a lot of subjectivity to food tastes. Go with the type of food you like.
In fact, you don't even have to do the full fledged luau to take in the culture. I don't know if they still have it (because Marriott's going through a renovation), but you used to be able to go sit poolside at Marriott's Kumu Grill in Wailea and watch traditional Hawaiian guitar and a Hula show poolside at night. The setting was beautiful (poolside with sweeping views of the ocean). The menu is A La Carte, with reasonably priced dinner sections and they have a bar area too. Some people just went there for drinks and appetizers, others had full course meals, and some were just there for dessert. Their main hula dancer is Native Hawaiian and was raised with the culture and taught by some of the best local hula teachers of the time. She shares a lot with the people in the audience, including inviting kids in the audience to come up and dance with her. I think they have a show every night at dusk - or they used. You should call Marriott Wailea to find out for sure, because that whole area is going through major change. Another thing to check out if you can, is Hawaiian Slack Key Guitar. They were playing it up at Kapulua (another area going through renovation and new ownership, so call before you go). Slack key is very local style and famous musicians, such as the pianist George Winston had some hand in the movement. Willie K is another famous local musician. He plays at Hapa's.