The best of Provo is certainly a 45min. boat ride (plus a 1/2 hr. shuttle ride) away. And since you're crossing between islands, not particularly calm. 2 tanks get you back to your hotel around 2:30 - trips include lunch. They just don't leave particularly early. Do a 3-tank and you're pushing 5PM.
But you can also stay in Grace Bay and dive from there and at NW Point nearby. NW Point is good diving, the liveaboards do a couple days there first. At Amanyara (very expensive) they have their own operator and advertise the reef is 500 yds. offshore. None of those dives are more than 10mins. out. Also the operators pick up in that area and take you to the boat.
So it could be doable. Provo is just really expensive though - at least as expensive at Grand Cayman - maybe more. And it's all boat diving. Really excellent beach - Grace Bay is one of the nicest in the world. Staying
on it is priced accordingly...
You might consider the USVI's/BVI's with some caveats. For under $700 Wilmington to St. Thomas is 6hrs. each way with one stop in Charlotte. There's a lot varying depth diving just off Charlotte Amalie - one of the best dives in the area - Cow/Calf Rocks can't be 50' to the sand. And shallow wrecks. Another option there is to dive from the East End. They dive the Cays nearby - most you can see from shore clearly enough to ID the dive boats and Coki Beach is a decent shallow shore dive there. They also dive around St. John - 1/2 hr. boat ride via ferry - I'm guessing less via faster dive boat. There's also a dozen dives off that side of St. Thomas within a 15min. or so boat ride.
From Red Hook there's both a people and a car ferry that run over to St. John where there's also about 1/2 dozen shore dives. And other operators that dive locally and sites a little farther reach for the St. Thomas boats - although many do go out there. We tried for Carval Rock, one of the better dives but it was blown out - went around the leeward side of Congo Cay and it was flat calm. Good dive there also. St Thomas Diving Club - located at Bolongo Bay Resort - is a good operation with a big boat. Slightly smaller boat at Red Hook Diving. All their staff is Instructors - even those that DM.
One other option might be to travel over to the BVI's and dive there. The way most people do that is via Fast Ferry - they're big boats and pretty stable. Takes about an hour from St. Thomas to Tortola - just under two to Virgin Gorda. And they're ultra-reliable - some friends left Virgin Gorda at 8AM for a 1PM flight out of St. Thomas. Got there early enough to stop for lunch downtown. The ferries run just about hourly between all the islands.
Virgin Islands Ferry Schedule
We dove from Virgin Gorda, used/liked DiveBVI.
Dive BVI >> British Virgin Islands Scuba Diving, It's What we do! They have a stable 46' Newton dive boat. And a big powered cat but it's more used on snorkel trips. Really valet service, they kept our gear, set it up daily on the boat and cleaned and dried it our last day. A friend has a bad knee so she sat on the back of the swim step on every dive and they brought her gear to her. We couldn't even help change a tank for ourselves - they did it all. The DM even defogged all the masks on the way out.
Most of the smaller islands are within about a 1/2 hr.-45min boat ride - but there's also a few sites 5mins. from their dock. Aquarium actually was a pretty good one. The deepest we went doing 22 dives there was 80' past that you were on the bottom. Some of the sites were closer to 60' - a few of the more popular ones had a hard bottom at 40' ish. The signature wreck there - the Rhone off Salt Island is 70' under the bow.
We were there in early spring (late March) It was pretty calm. IDK how it would be in Winter. But contact DiveBvi if interested - they're really helpful people. Ask for Casey - their GM. 1-800-848-7078
You can also fly to Beef Island on Tortola from St. Thomas but that used to be only during the summer months due to demand. Virgin Gorda has a small airstrip - day flights only. There's one operator that flies 4 place Cessna's in there. There's also a helicopter but that's big money I'm sure. Richard Branson's (Virgin everything CEO) private island is just off the north end of Virgin Gorda and Little Dix Bay is also very pricey. Outstanding beaches also - some so private the only way you get there is via resort boat. No crime that I saw either - we rented a villa and they had no external door keys - never needed them. Only 3K people live there. Never stayed there but I like the looks of Mango Bay Resort. The reef (for snorkeling) is so close there boats can't enter the bay.
Bonaire is the same reef as Curacao. But the shore entries are a lot more difficult - most over ironshore/coral rubble at the waterline instead of beach. I'm getting to old for that also...