
If you ever find yourself in FWB around meal time, I just tried Stweby's on Racetrack Road about a block east of Beal Pkwy. The fish is fresh off the docks in Destin, the oysters and shrimp are from Apalach, and $7 gets you a sandwich or two tacos and fries. Been a long time since the two of us have gotten out of a fish place for less than $20 including drinks.
http://stewbys.com/
I think what lets them hit their price point is that land costs/rent along Racetrack are pretty reasonable compared to a lot of places.