I definitely recommend the Fia Fia
We were there last August, originally booked Paradise Cove Luau but then changed our mind based on some of the recommendations on this board and went to the Fia Fia instead.
Oh we were so glad we did that. I had never laughed so hard during a luau! I can not comment on the Paradise Cove since we canceled that one, but I had been to traditional luau before in Maui at Royal Lahania. Fia Fia is ten times better. If you have kids, they will let them sit around the stage (which is just a slightly raised hill on the lawn). We had a great time.