Bonaire, Netherland Antiles; amazing place. I dived with Divi Flamingo dive shop, very friendly and competent people; very decent, recent ScubaPro equipment.
On Bonaire you can dive from the shore; if you pay for a boat dive in the morning, you have unlimited air for the rest of the day, to use wherever you wish.
Try night dives, Tarpons are pretty smart, they figured out that the dive lights are good for hunting, so they follow you around and hunt in your lights, quite amazing; turn the light off - and they will bump you: "Hey, buddy, turn on the light!"...