If you find yourself at the airport (the Continental side) the restaurant upstairs serves the very best "local special" that I've had!
Otherwise, my favorite was the park (sniff sniff)... what about that place across from Coconets? I heard it's good there but haven't tried it.
I'll keep thinking...