The most common accommodations on Provo are condos located on Grace Bay, which is one of the most beautiful pink powder beaches anywhere. I would agree with koozemani, the Royal West Indies are one of the best of these condos; wouldn't hesitate to stay there again.
The units I've stayed in have had nice accommodations with full kitchens and even a washer/dryer (pack light-take home clean clothes!). Many have a terrific ocean view (ask).
They have a very good restaurant on site, too convenient.
Food & beverage prices are indeed high, even in the large IGA market. We saved some money by using the fridge and filling it with breakfasts, snacks, and drinks from the IGA and the Wine Cellar. We didn't have to go out for every meal or drink, gave us the opportunity to relax on our balcony, or walk on the beach.
We've used Dive Provo on several trips and recommend them. They have packages that include a number different condos and hotels. They will pick you up every morning, keep & clean your gear, and set it up for the next day's dives. They maintain boats on both sides of the island and will take you without hesitation (or extra cost) to distant sites every day; first class operation.
Provo is real dive destination, that it has non-stop flights from the East Coast, makes it also one of the most accessible.