Question for expierenced divers/world travelers

[Scubaal]

One place you listed that would meet most your requirements (minus shark dives) would be Bonaire. Very easy diving both boat and shore. Do as many or as few boat dives as you or your wife would like. Then grab a couple of tanks and do shore dives.
One down side to Bonaire is, there at least seems to be quit a bit of petty crime. If you check out scubaboard.com you can find endless decisions on the subject.

Al