Would highly rec Southern Cross Club on Little Cayman (http://southerncrossclub.com). Seems like it would fit all your needs and was a great time. The diving and staff were great! The food was good (not fancy but plenty to eat) and the night-life consisted of night diving or hanging around their small bar or keeping yourself busy (I was on my honeymoon...). Would go back for sure.
Rich
Rich