fraserm, where do your parents actually want to go?

Before getting too bogged down in the relative merits of Mauritius versus South Africa etc. as a place to start, I'd focus first on where they actually want to go.

As has been pointed out, there are some places in Asia (South Korea or Indonesia) that, from a price point of view, may be a good place to start. Japan may also be a reasonable choice - currently about $7,300 for a DONE4. Singapore and Hong Kong are rather more expensive. However, the real question comes back to "where do your parents want to go?" Only when you have some reasonable idea of that does it make sense to start getting into the specifics of where to start.

It is also worth remembering that the trip doesn't have to be done in a single 'journey' - you can stop off 'at home' for a while and then continue on, depending on where you start from, where 'home' is and where you're going.