And when you ask for Mahi Mahi or Dorado you'll look like a tourist in the Keys.
If you can get into Blue Heaven in a reasonable amount of time then eat all the things. Their food is legendary for a reason.
There's no good BBQ on the rock. At least not last time I was there. The one next to Green Parrot, Charlie Mac's, is OK. It's owned by Pat Croce, the same guy who owns Rum Barrel, Island Dogs and the Green Parrot. I liked it much better when it was Babalu's. Their New Haven pizza was amazing.
If you want exceptional food and don't mind eating it from a trailer/food truck (though they also have a sit down area), go to Garbo's Grill at 409 Caroline. You can't go wrong. It's consistently listed as one of the top food trucks in the United States and one of the top places to eat in the country. I've not been to the new static location, but all my friends go nuts for it.