I just ran through the Delta Airlines list for visa required by Ukrainians, and here's what I picked-out as places one may want to travel with a Ukrainian (don't ask me why):
http://www.delta.com/travel/trav_serv/intl_travel/timatic/index.jsp
NO VISA from US
---------------
U.S. Virgin Islands = if USA resident
British Virgin Islands = 14 days if USA resident
Puerto Rico = if USA resident
EASY VISA
---------
Cyprus = visa on arrival
Jamaica = visa on arrival for tourist to 3 months
Marshall Islands = visa on arrival for tourist to 3 months
NO VISA
-------
Antigua/Barbuda = 1 month
Barbados = 28 days
Dominica = 21 days
Dominican Rep. = 90 days + tourist card on arrival
Ecuador = 90 days
Grenada = 3 months
St. Lucia = 28 days