Africa.
You need several injections (though check out the malaria protection carefully: In the past many argued it was almost useless) which seems to deal with one of your criteria. They have thieves and criminals too. Seriously, you need a bit of caution and watchfulness but don't let that put you off.
In 1986, 1990, 1992 and 1994 I and then girlfriend, now wife, went there - Kenya, Tanzania, South Africa. The whole wildlife thing is mind blowing, closest thing you will get to that trip to the moon in terms of being different. You can do a bit of former colonial luxury in the cities coupled with some roughing it in the wild.
Though if you have the money, you can do fantastic luxury in the wild too coupled with regular forays into the wilderness to see the local lions cheetahs etc eating the local deer type things. In tent one night in Masai Mara we paid a local young lad 50p to sit by a camp fire outside for the night in case lion or similar came by. Hippos barking (sounded like barking) kept us awake another night. Lion chased jeep. Etc.
15 years on, encumbered with children, we look back at it all as having brought some of the best experiences of our lives. The photos are still on the walls of the house, and others are brought out regularly to show the kisd what exciting people their parents once were. Not just a holiday, but an investment in the future in the sense of giving you memories and a sense of wonder that will last years and years...And to think we could have put the money into a pension product instead....
