Our first night we went to the Pelican Grill restaurant, just a block down the road from where we were staying near the Store Bay beach. Pretty good food, plus the waitress was real nice and helpful.