Our cruise itinerary was changed/shortened for this question I originally asked and St. Thomas was dropped. We instead did HMC, Key West, then back to port in FLL. Even though we'd only gone to the cruise line's private island, we still had to clear immigration at our first US port of call (Key West).
On arrival in Key West, ALL passengers had to clear immigration. Those with excursions were called first I think starting at 8 am. Then starting at I think 8:30 you were assigned a time slot deck by deck. They announced it and there was a letter in your cabin the day before with times and instructions. I don't think the scheduled clearing times lasted more than 90-120 minutes in total.
They had us queue on deck 3 through the atrium and shops, and there were USCIS officers checking passports in one of the meeting rooms. After the check, a crew member punched your key card and you could exit the ship or go back to whatever you were doing.
We had an excursion so were in the first group allowed through the line. Took about 10 minutes and moved very quickly. It was quite efficient.