Paul - I walked in the door 10 minutes ago from my flight back from Key West. Here's what I found, who I used, etc. Keep in mind I'm a new diver (my dives were #'s 2 thru 7) so my opinion may not be as relevant as some others might be.
Dove with Sea Breeze on Sunday for a sunset dive (not a night dive) because we had some snorkeling friends and a friend coming in early afternoon, i.e. not early enough for a 1 pm excursion. This was a great boat for a number of reasons. The crew was absolutely fantastic (better than the other two later in the week which were more traditional LDS's). Very friendly and entertaining. We had about 13 people on board a boat that could hold about 35. The other great aspect of this operation is the sunset portion--while the rest of the goons are waiting on the pier for the sun to set, you're out catching one of the better sunsets you'll ever see from a prime location. Plus the beer and wine are complimentary =-) . I believe they are 1 of only a few that do these sunset dives. The dives themselves were also in different locations (again, other 2 were the same spot). Not sure of the name, both reef dives, both great. They are located at the very end of Front Street, which is the last street on the right headed northbound on Duval.
Monday dove with Lost Reef, which as posted has been around awhile. 9 am dive produced just 3 divers and a snorkeler, and 1 diver bailed, which made two. Crew was friendly, we headed out to Rock Key and Sand Key for 2 dives. These are apparently two of the spots that most shops tend to frequent, and it's kind of a shame because you can't even trick yourself into thinking you're in a different place because there's the enormous Sand Key lighthouse right there to let you know you were there two days ago. Crew was friendly with Lost Reef, but again there were only 4 of us so who the hell else were they gonna talk to?
Wednesday was Subtropic, and despite the recommendations I found the crew to be significantly less personable than the other two. Maybe it was a bad day. I think their strong reputation might actually be hurting them a bit because the boat was a shade overcrowded. Same deal, Sand and Rock Key.
Anyway, the water was basically bath temp--after about an hour per dive without a wetsuit I was very comfortable temp-wise everytime. Saw all the usual stuff (but, disappointingly, no shark), including most memorably a 4-foot barracuda which we gave a berth as wide as he wanted. Also some tarpon that were in the same 4-foot range; beautiful, big grouper, enormous lobster, etc. Also be on the lookout for a huge stone wheel (I believe on Sand Key, ask your DM about it) that apparently was used way back as a mooring to quarantine big ships but was knocked out by a hurricane (in the 50's?) and ended up on its side against a reef. Must be in the 15-18 foot diameter range, and pretty neat.
If I was going back next week (damnit, I wish I was!) I'd head back to Sea Breeze for the different dives and the terrific crew.
Anyway, hope this helps, and happy diving!
Brian