Again I will have to stress that I think Bahama Divers is a decent dive shop. They are much less commercialized than stuarts cove. SC is all about volume and drops the ball when it comes to customer service. BD does much better from that aspect. I picture SC as being a company that would leave people behind because of how much volume they are doing. I have dove with both. If you want to do a shark dive, SC will do it. The blue hole is cool, but just like anything you could dive it and there will be no sharks nothing that day. That is probably less of a chance though. It does suck having to make the long journey from Paradise Island to SC. So if you are staying on PI then bahama divers is great. In my mind all the diving is the same except, one goes to blue hole one does a shark dive.
I take great exception to the comment about the Fish Fry. Definitely go to the Fish Fry! Yeah the service may suck, but who cares. Its where locals go and its fun! Stop at one place for drinks and conch fritters (way better than any on the island) and then move one for dinner. It looks bad down there and if you go out back you can probably see rats in the trash cans and 1000s of broken conch shells, but do it because that is part of the experience. Of course if you are staying in the Royal Towers of Paradise Island than you probably are too snobby to get dirty anyway...haha...hopefully not!