Hello. It sounds like quite a trip!
I have a place on St Thomas and have some perspective. A lot of factors should be considered in choosing a dive operator. How much time do you have in port? How much time do you want to spend diving: Full day, half day? 1-3 dives? What type of dives do you want to do: reef, wreck, night?
If you have limited time, then staying close to Charlotte Amalie is smart. The traffic is pretty congested and getting out to Red Hook could take up to 1/2 hour. I know that Chris Sawyers' morning dive leaves the dock at 9:00. Afternoon at 1:00-1:30. If you wanted to make a full day of it, however, I would recommend Chris Sawyer. Also, there are some pretty good restaurants in Red Hook!
Joe