Restaurants in Naha

Has anyone got any recommendations of where to eat in Naha? Posh, cheap, something different. Anything really!

I think the restaurants on the 2nd floor of the Heiwa Dori public market are a lot of fun. Other than that, Okinawa has a bunch of A&W's that might be nostalgic for some. If you ask the locals they usually rave about Okinawa soba, but I don't know if it's worth seeking out a specific shop.

If you do go to that market, the bottom is the fish store and the 2nd floor is the restaurant. Once you buy your fish, the 2nd floor restaurant can cook it for you at the spot! Make sure you shop around. They are notorious for trying to push you to buy the more expensive items. Go around and negotiate based on what you want. It is fun! Beware, they do allow smoking at the 2nd floor restaurant :(

There is a plaza near Todaiji Temple where many Nara's old nad new restaurants get together. Make sure you eat Nara's famous Kaki-no-Ha Sushi (a type of Sushi wrapped with persimmon leaves).

http://www.yume-kaze.com/en.php

jomonstrider, the question was about Naha in Okinawa, not Nara :)