Go to Turks & Caicos. Its Caribbean but safe and pristine. It can be expensive. Check out a singles group that has a trip scheduled for 4 nights:
http://www.singlescruise.com/resortd...ngles-vacation
You can save money by room mate matching or your own room for a single supplement.