Pick several places you'd like to go. Call UA and see what is available. Also check with Amex/Starwood partners such as Delta or with Starwood I believe you still have AA and US.
Be flexible on time for best shot. When I did South Africa I called with a 40 day window and said find me a two week trip. ended up with 18 days near start of my time slot. Did the same for Australia.
Fly business or first class for best value.