I cant help you about specific restaurants as I havent been there. I would suggest you to try the local food and especially any fish roasted over charcoal. Aegean sea is full of extraordinairy fish. The best fish you can find is Sfyrida(epinephelus aeneus). Then some other amazing fishes are synagrida, rofos, tsipoura. Be aware that most big fishes are expensive per kilo.