First of all, EVERYTHING is pricey on the island. So expect to pay more than you pay at home for every type of restaurant from fast food to haute cuisine. There are many great places to eat on the island and you'll go nuts (and broke) if you try to hit them all. Pick a few and enjoy!
BURGER PLACES: We ate at WAY more burger joints than we thought we would, but for good reason -- they were great! Most places use the local beef and charbroil them.
Burger King - I only mention this one across from Kukui Mall because they have a Playplace. The dining area gets real warm so eat at the outdoor tables (but watch out for chickens).
Beach Hut - Located near Kalapaki Beach, this funky shack serves up not only beef, but buffalo and ostrich burgers! We didn't try the last two, but the beef burgers were great. Very friendly folks, too. Eat upstairs for a view of the beach.
Duane's Ono Char Burger -- On the highway near Anahola Park. My wife is a big fan of the Bleu Cheese burger at Red Robin and she said the one here at Duane's beat Red Robin hands down! The teriyaki burger also is excellent. Be advised that there is no restroom and the flies at their outdoor seating area were pretty bad so you might be wise to get your burgers to go and take them to Anahola Park.
Poolside Grill at the Embassy Resort -- I mentioned this in my accomodations review, but I'll reiterate that they have great burgers!
CASUAL PLACES: Actually, just about every place on the island could be considered casual. But these are not the "fancy" places.
Tomkats Grill -- This Koloa bar and eatery is located in the old movie theater and is decorated with a feline theme. Although the service from our un-smiling waiter was kind of brusque, the burgers and chicken were quite good. They have salads and fish as well.
Pattaya Asian Cafe -- This Thai restaurant in Poipu Shopping Village was a bit of a disappointment. We eat a lot of Thai food so maybe we're overly critical, but we thought their food was only average quality and the portions were small. Our 12-year-old proclaimed the fried calamari as "excellent", though.
Shipwreck Subs -- Also in Poipu Shopping Village, the subs here are excellent and huge which justify the (fairly) high prices.
They also have shave ice and Tropical Dreams ice cream that was touted as better than the more well-known Lappert's, although I thought it was comparable.
Brick Oven Pizza -- Located on the main highway in Kalaheo, the guidebooks say this is the best pizza on the island and they are right. Try the excellent homemade sausage topping. Good sandwiches and salads, too. Friendly service.
Keoki's Paradise -- I include this in the casual restaurants because of the atmosphere so it's very popular with families. You'll spend as much on the food here as you will at the fancy places. My wife had the HUGE prime rib which she proclaimed to be as good as any she's had at our favorite mainland steakhouses. We made leftover sandwiches from it for a few days.
My opakapaka was perfectly done. Our one regret was that we had no room for their highly regarded Hula pie. This restaurant is run by the same folks who run Dukes's and Kimo's so they are very consistent and service is always friendly.
FANCY PLACES: There are many high end restaurants on the island. Some that we didn't eat at but heard good things about are Tidepools (at the Hyatt), Shells (at the Sheraton) and Pomodoro (in Kalaheo). We intended to go to A Pacific Cafe since we enjoyed the one on Maui but we decided we didn't feel like making the drive from Poipu to Kapaa.
Roy's Poipu Grill - Anyone familiar with Hawaii knows that Roy Yamiguchi is THE restauranteur on the islands and his Poipu Grill (in the Poipu Shopping Village - it's location is nothing special) did not disappoint. Unless you want to dine fairly late, plan on calling at least a day in advance. We had a marvelous sushi salad to start. My wife had a lamb and scallops combination and I had ahi that was done to perfection. We didn't have room for their specialty chocolate souffle dessert so I opted for a simple sorbet. If you're not into fancy food presentations (my ahi was not only delicious but a work of art), you might find Roy's a bit pretentious. Our friendly waiter was just casual enough to remove any air of pretentiousness.
Beach House - Run by the same folks who run the excellent Plantation Restaurant at Kapalua on Maui, this is THE special occasion restaurant on the south shore. We dined there well after sunset and weren't able to enjoy the view, so call way in advance to secure a window table around sunset. The food and service are excellent. We started with their calamari appetizer which was very good but nothing special in terms of preparation. My wife had sea scallops and I had their signature macadamia crusted mahimahi which were both done perfectly. This mahimahi preparation may be a Hawaiian restaurant cliche but the sauce was superb and the fish was very fresh and flavorful.
My wife said the scallops were among the best she's ever had. Once again, all I had room for was sorbet for dessert.
Casa Di Amici - This great find is located on a side street near Poipu Beach. There were so many great choices on their menu that we found it hard to decide. My wife opted for a seafood paella and I went with ahi (can't get enough of this fresh fish). Both were fabulous! We split an excellent Caesar salad, served with anchovies to my wife's delight. Service was very good and they have outdoor tables although the location is nothing special. Several dishes are available in two different sized portions which is a nice option. You definitely want to save room for dessert. Their bananas foster (for two) is very good but what you really want is Baked Hawaii. This was definitely one of the dining highlights of our vacation. Coconut mango sorbet on top of a chocolate genoise cake round enclosed in meringue and then flamed with framboise. The whole thing is surrounded by a raspberry and lilikoi sauce.
For $7, this one of the best dining values on the island! We enjoyed it so much that we brought our 12-year-old son back the next night for dessert for his birthday. He loved it! They also brought us a half order of the bananas foster and the chef later appeared tableside to chat.
PLACES TO AVOID: Two places that we didn't go to because of bad guidebook reviews that were confirmed by other guests at our resort were Pizzeta in Koloa and Brennecke's in Poipu. Although it was crowded when we went by, we were told that the pizza at Pizzeta is mediocre and the crust is soggy. Brennecke's is a landmark and has a fantastic location but for the price we heard that the food and service were decidely below average - strange for such a well known place. We did have made-to-order sandwiches from their downstairs deli and they were excellent. Take them across the street to Poipu Beach park for a nice picnic. The friendly cashier told me that the deli gets very crowded from 11:30 to 12:30 so avoid those times.