Since you don't like to repeat the same destination much, if at all, and your desires may not change for some time, I suspect it may be worth looking at the options broadly, not just which one looks best this hoped for trip.
You want to dive a lot, but your idea of a lot sounds like averaging a little over 3 dives/day. Off the top of my head, here are some places (skipping live-aboards because of the non-diver) I believe can do that:
1.) Bonaire - if you shore dive. The glory of Bonaire is shore diving, often 4 - 5 dives/day. You can boat dive, but it's not a sandy beach place (a few exceptions: I hear Harbor Village and I think this new
Delfins Beach Resort). Arid island, has a rugged beauty if you know how to look for it (mostly up north), but I don't think this is the droid you're looking for. Airfare is killer but costs on-island not so awful (food's expensive), especially if you do a lot of shore diving & drive cost by dive count.
2.) Curacao -described as similar diving to Bonaire, larger island, not as convenient getting place to place, more topside, and you get sandy beaches. Judging from reports, a lot of people shore dive it, but a lot of people do at least some boat dives (vs. Bonaire where a lot only shore dive). Here are some threads comparing the two:
Curacao vs. Bonaire -
http://www.scubaboard.com/forums/lesser-antilles/473036-curacao-vs-bonaire.html
Bonaire vs Curacao -
http://www.scubaboard.com/community/threads/bonaire-vs-curacao.535918/
Curacao 1st Timer Trip Report -
http://www.scubaboard.com/community/threads/curacao-1st-timer-trip-report.527457/
Curacao Trip Report -
Curacao Trip Report
Curacao Suggestions -
http://www.scubaboard.com/community/threads/curacao-suggestions.536523/
Place to stay in Curacao -
http://www.scubaboard.com/community/threads/place-to-stay-in-curacao.518346/ See Damselfish Post #3.
Curacao Trip with Teenagers in June -
http://www.scubaboard.com/community/threads/curacao-trip-with-teenagers-in-june.525886/
Curacao Lodging -
Curacao Lodging?
Curacao - First Time Opportunity -
Curacao - First Time Opportunity
Curacao Solo Diving with Cert. -
Curaçao solo diving with cert
3.) Cocoview Resort, Roatan - boat dives supplemented with shore diving the large house reef with a wreck present. Are you not wanting to go back to Roatan, or just not to Anthony's Key Resort?
4.) Turquoise Bay Resort, Roatan - I think you can get 3 dives/day. Scubadada had a nice report on it that was complimentary. Boat diving, not shore. A popular budget option I've seen listed before by a number of local dive group organizers. I think 3 dives/day?
5.) Cayman Brac Beach Resort, and Little Cayman Beach Resort. They can do 3 dives/day. Rather small islands without much topside, though (more on Brac than Little, I'm told); I don't know about their beach scene.
6.) Grand Cayman - already discussed. Sunshine Suites Resort and Comfort Inn Suites are the 'walking distance from 7 Mile Beach' budget options that drew my eye when I was looking at it. You can find op.s offering 2 2-tank boat trips/day, but cost may get you. Shore diving may start to appeal...! There are a range of excursions (e.g.: some controversial, like dolphin encounters & the Turtle Farm).
7.) Key Largo, Florida - Rainbow Reef Dive Center. 4 Boat dives/day quite doable. (
Trip report 2013). I don't know if the hurricane damage will be an issue when you travel. Not a sandy beach destination, though.
8.) St. Croix - I went last August and enjoyed it (
thread on St. Croix).
9.) Cozumel - Wow. So many options to research. I've been collecting notes for months hoping to spend a week there someday. IIRC, the southern A.I.'s may offer you sandy beach. The in town options offer you a range of dining options many people praise highly. When you research Cozumel, you may find people talk food 2nd to diving. Cozumel is a (major) cruise ship port, so expect a lot of excursions to be available.
On marine life: 8 trips to Bonaire & I haven't seen a shark. I saw a few in Key Largo, several in Belize, the Caymans & St. Croix. More large grouper in all of those than in Bonaire (where tiger grouper were about it for big ones).
If you can accept some shore diving & total trip cost doesn't bite too hard, I can't imagine you guys won't like Grand Cayman. For a quainter experience, St. Croix was fine for us. There sheer # of Cozumel reports & multiple repeat visitors can't be wrong!
You got analysis paralysis yet?
Richard.