MMario, I could offer lots of opinions about Australia, but instead I would encourage your parents to definitely visit Fiji, particularly given your father's WWII connection. As I understand it travel there is extremely good value. More importantly, even at the height of the conflict some months ago there was little danger to foreign travellers.

Regards, John