We dove last year with TIDivers. They're located just south of the Treasure Island resort on SMB. Good dive operation, 3 boats with small groups, they left us alone to do our own thing and also escorted anyone who asked or on deeper dives. I don't think we ever exceeded about 12-15 people on our boat except for an afternoon Dive/Snorkel trip to Stingray City. Since they're on SMB, they advertise that they get to the sites quicker, but I don't know if this was true or not, there was only one time that we had another boat near us during 4 days of diving, there's a lot of divesites on the West side of Cayman. They'll pick you up anywhere along SMB if you call them, but judging from the number of diveshop vans I saw so will just about anyone else. They also dive the South side pretty regularly depending on the weather.
I had heard Red Sail catered more to the cruise ship groups with their schedules. Also they have a couple of larger boats which generally means more of a cattle boat approach. And they were slightly more expensive than just about anyone else which is why we didn't consider them.
I also had exchanged e-mail with Don Foster's they're around the Comfort Suites area, we almost booked with them until we realized our condo was walking distance to TI Divers.