PastorG is spot on.. I will second the use of Stuart Cove’s in Nassau. Used them in the past and they work well with the Cruise lines to get you back on time. They have some great dive sites such as movie sets and the awesome "Tongue of the Ocean" wall to see or you can do the shark dive. One dive with sharks in the water and the second kneeling in the sand while they feed them. I’ve also done the Cococay dive.. Not much to it. Like mentioned earlier, it’s a guided tour by Sea Trek (Royal Caribbeans’s Water Sports name) About a 100 yard surface swim and then you go to the outside of a large rock barrier and go along the side of the that. We did see an eagle ray and lobster and some smaller Caribbean fish. It was fun to blow some bubbles but not a "gotta go back" type dive. Can’t help much with the Key West part. Each time I go there, I’m more on a liquid diet and don’t dive. Although, if you can squeeze in a Vandenberg dive, I would do that. I just have no idea how the timing goes with the cruise lines.
Hope you enjoy..
Dale