My father-in-law and sister-in-law are no-fish vegetarians and thus we were worried about the prospect of two weeks on the Big Island with them, but nearly every town has at least one natural food market and one or more of tofu, seitan and tempeh are served at nearly every restaurant we went to -- one even had loco moco with fried tofu!
Ba Le, next to the KTA on Palani Road - good Vietnamese sandwiches, decent pho, good bun. Sandwiches are expensive if you're used to the $2 variety but they're very good. Vegetarians can get tofu in just about anything, and they even have a mushroom broth made without MSG and without fish, so you can get a kind of pho if you like.
Farmer's Market on Ali'i Dr. - just don't bother. There were maybe 7 or 8 vendors actually selling produce all at ridiculous markups. If you do go, make sure to bargain for your produce or you'll end up paying $1 per lime. If you can bargain in Pidgin it will serve you well. The market over on Kaiwi St. in the industrial park is better but still has the dual-pricing scheme.
Hang Loose, at the north end of the Kona Inn shopping centre on Ali'i Drive, had good sandwiches and salads at only slightly extortionate prices. (Food in Kona is very expensive.)
Michaelangelo's, across from the Outback Steakhouse near Huggo's on Ali'i Drive, had very nice Italian food in a beautiful setting overlooking one of the swimming beaches. The service was very nice and the food was really quite good. It's expensive -- sit down restaurant, and one of only two places on the island where I saw people wearing khakis -- but the food is very good. They have a very large vegetarian selection.
Kona Ranch House, on Kuakini Hwy. just east of Palani Rd., had extremely well-priced breakfasts with a ton of food. $6.95 got me two eggs, my choice of meat (including smoked pork, Portuguese sausage and SPAM), my choice of potatoes, and toast or two huge pancakes with toppings. Ask for flavoured syrups such as coconuts. Parking is difficult since the lot is a victim of the modernisation of Kuakini Highway -- you can park in the Long's/Sack 'N Save parking lot and walk the block.
The best fish in Kona is actually at the KTA on Palani Rd. -- get there around 10 AM for the freshest cuts. Sashimi-grade ahi was $8.95/lb. and cooking-grade ahi was $5.95/lb., though the price varies daily on the catch. I asked the fishmonger behind the counter if I could smell the fish (it's sold on meat-style trays covered with plastic) and he not only let me smell it, he cut off a small piece so I could taste it. It was absolutely terrific and I made a big bowl of homemade poke out of it. The fish at Sack 'N Save was expensive and the fish at Safeway smelled terrible, like it had made the journey from Hilo in an unrefrigerated truck. (I complained about the fish to the manager at Safeway and he said "If you think is junk, no buy!")
Don't call it Kamuela -- the post office decided there were too many Waimeas in Hawai'i and so they unilaterally renamed the town Kamuela, after Samuel Parker, whose ranch is the largest in the islands and one of the largest in the country. Even the road signs say Waimea.
We hit the food court in the Parker Ranch Centre -- I went to L&L's for my fix (mmmm, chicken katsu and spam musubi!) and my wife went to the Korean place in the food court. The Korean food was surprisingly good, and the kimchi was very spicy. The Chinese food from the same place was boring and overcooked, oddly enough.
Tex's Drive Inn's malasadas -- get the guava, get the liliko'i custard, and get the plain custard. Mmmmm! There's a Tex's on Hwy. 11 near the Ka'u hospital too.
The farmers' market was very, very good. Wednesday mornings and Saturday mornings are when most of the vendors come, though it's open every day, and increasingly Thursdays are crowded since a new cruise ship pulls in then. You can still bargain for your produce but there's less need here, and much much much more in the way of produce. If you speak Tagalog or Vietnamese, you'll get terrific discounts on bakery goods (red bean buns, banana lumpia) and Viet appetisers (summer rolls, spring rolls, papaya salad). If you're going to buy fish to eat raw, get there before 10 AM or he'll sell out.
There was produce here that I have never seen fresh outside of Vietnam... rambutans, longans, mangosteens, calamansi, mamey sapote, etc.
Up mauka from the main produce section of the market on Mamo St. is a Filipino bakery which name I disremember... but they have fantastic sausage buns, terrific sweet lumpia and great "upside down" muffins for ridiculously cheap prices.
Ken's Pancake House, on the intersection of Kanoelehua and Kamehameha/Kalanianaole (Four Mile) - universally panned in all the visitor's guides, and I'm not sure why. The coffee was pretty bad but the food was actually very good, for breakfast at least. I had Portuguese sausage, rice, and pancakes with liliko'i (passion-fruit) syrup, which was very good. They're open 24 hours, the only restaurant on the Big Island to do so.
Hilo Bay Cafe, next to Le Mart du Wal across from Prince Kuhio Plaza on Hwy. 11, was the only "California-style" restaurant we found. It was very crowded and the service was abysmal -- we were tucked away in one of the big booths in back and they pretty much ignored us -- my wife's grandfather had to get up and walk to the hostess to get pretty much everything. He did something he'd never done -- left the tax amount (4.167%) as a tip. The food got mixed reviews -- I found almost everything underseasoned except the French onion soup -- and given that French onion soup is nearly always TOO salty, this fits in well. My wife had a softshell crab sandwich which was overcooked and underseasoned. Her stepmother had an ahi sandwich that was much better with the liberal application of aioli. Her father had an heirloom tomato salad (very good) and "spanakopita" which was seasoned potatoes in a lumpia shell -- the spinach and feta were in a salad on the outside. Her grandfather had sashimi and it was the best thing in the place. It's owned by the same folks who run the Island Naturals food store across the plaza. This was the other place where people were dressed formally (for Hawaiian values of formally, meaning no flip flops and no tank tops).
One night in Hilo we wanted pizza. There are exactly two places in Hilo from which to get pizza: Domino's and Pizza Hut. I was astounded. We went with Domino's ("Hawaii's Ohana Pizza" [sic]) and it was, unsurprisingly, exacly like Domino's everywhere else in the world. Domino's wins for not charging for delivery to our house, which was way out at the end of Four-Mile (Kalanianaole) Street.
Terrific ice cream that wasn't overly sweet at the Homemade Ice Cream shop on Kalanianaole Road about two miles east of Ken's Pancake House.
For fish in Hilo, go to Suisan Fish Market early, or go to the KTA on Hwy. 11 -- don't go to the one downtown, it's dirty and the fish is bad and expensive. Fish was almost twice as expensive in Hilo as in Kona -- first of all, the fishing boats go out of Kailua which means you have to pay for it to be brought to Hilo, and second of all, the catch wasn't as good that day.
My wife's family all lived in Pahoa for a long time. Pahoa is very, um, interesting -- it's the Wild West type of mentality, where people don't bother with buttoning shirts or wearing shoes, and they all are very interesting people. A lot of them seem like Witness Protection relocatees, others are clearly pakalolo farmers, and still others you just don't @$#% with (though Johnny Ke'aloha, the haole-hater, is no longer with us). The restaurants in Pahoa reflect that, with the exception of Paolo's which is a fancier Italian place that sticks out like a sore thumb. Food's good, though, and you can go in dressed however you want as long as you're wearing shorts or pants.
Luquin's Mexican actually had good carne asada and good burritos, the salsa wasn't bad and the chips were fresh -- but skip the margaritas, clearly they got the recipe out of a book written by Norwegian teetotallers. Service was really terrible, even by Hawaiian standards (which are much more laid-back)... my wife's uncle had to go in the kitchen to give our orders.
The Thai place was closed (no sign telling us why, just closed) and so we went to the Lava Rock Cafe. It was slow, but that wasn't a bad thing -- but the waitresses all seemed really stressed out, which is very unusual on the Big Island, where the prevailing attitude usually seems to be "whatever, it'll happen tomorrow". The food was really good and, surprisingly, they had tempeh and tofu for the vegetarians in our group -- including tempeh fajitas. The coconut cream pie was really good and the liliko'i cheesecake was fabulous.
As you head south on Hwy. 19 out of Hawai'i Volcanoes Nat'l Park into the desert district of Ka'u, you'll pass through Na'alehu, a one-horse, one-room schoolhouse town about six miles east of the turnoff for Ka Lae (South Point). As you enter town from the east, the first business on the mauka side of the road is a little produce shop/bakery/pizza place with no sign over the door. The pizza was actually very good, and the guy behind the counter was really nice and quite talkative. They have good sweetbreads, though they only have non-diet sodas and no ice (it's all vaguely kept cold in an ancient refrigerator). The price was very good for the pizza and it's clearly the gathering place for the town, as everyone kept coming in. Ka'u has a reputation amongst those in Hilo and Kona as a deserted place with people who'd rather you weren't there, but I've never had that experience -- there's not much to do if you're a tourist, so most people just breeze right through on the way to Volcano or up to the coffee plantations in South Kona.
The Aloha Cafe next to the Aloha Theatre in Kainaliu, South Kona, had really good loco moco. Unfortunately the tofu scramble was almost totally tasteless and so my father-in-law was very unhappy. There was a lot of good food there and the service was good... my wife had mahi-mahi sandwich and it was very, very tasty and her sister had a plate of pasta with some really excellent marinara sauce on it.