I want to thank everyone for their replies and opinions. While no decision yet, we are leaning towards the Carambola Resort in St Croix. This looks like the perfect mix of diving for me and the sort of things my wife likes to do.
She's leaving the choice up to me. The Sweet Bottom Diver Center looks perfect for me and the diving first rate. Couldn't go wrong with the Cayman Island choice, either!
Thanks again
You will have a great time! Here is my writeup of the trip.
Contact the SBDC to chat with Tim Linse or any of the others about the specifics, decide the need for car rental, etc... they are very helpful.