Texas,
I lived and ran boats out of Key West for about 11 years. There is no truly outstanding dive operator in KW. All of the majors are about equal. They all dive the same sites. It just depends upon the crew, and the day. If I recall correctly, Coconut Beach is on South Roosevelt (resorts change ownership and names quite frequently). If this is the case, Key West Pro Dive, or Subtropic, would be the most convenient. Southpoint, and Captains Corner are downtown where parking can sometimes be a problem.
I don't know of any regular operator who uses 100's or steel, but that may have changed--call around.
Runs are normally about 20-40 minutes, depending upon whether they are going east to the Sambos, south to the Cayman and Tug, or west to the dry rocks' and Sand Key.