Just returned from Key West about 3 weeks ago. You can see my photos and video here to get what to expect:
http://www.mosesong.com/travel/keywest09/index.htm
The Vandenberg is pretty cool. I enjoy it better than Key Largo mainly because there are more stuff to do outside of water. I think Key Largo has more deep/wreck dive.
I used LostReefAdventure (http://www.lostreefadventures.com/) as our dive shop. The dive shop is right by the dock, so it’s convenient and the crew are helpful (although the owner seems to be not that out going). They have 20% off if you do more than 3 trips with them.