This supports the inverse square rule for seafood restaurant quality vs. being near the ocean. There are good places, but right on the water? Universally bad.
The way I think about it is this: the restaurant has to pay for the real estate, and that cost must get factored in somehow. Water views aren't cheap. So you can get good food on the water, but you'll be paying for the view.
Conversely, I have one piece of life advice for you: Don't eat seafood in Alice Springs.