As Australia has so much tar, I would be inclined to go for a big touring bike with dirt capabilities, like a BMW 1150 or KTM 950. These will give you more comfort when touring 2 up than a smaller 600 to 650cc bike.
I personally prefer the KTM 640 Adventure for solo travel, but I have found that while it is excellent in the dirt, it can be a little uncomfortable for doing lots of kms on the tarmac. Hence, far better to go for something slightly more road orientated in Oz. After all, it is probably unlikely that you will be riding on rough fire trails with two people.
Having said all that, I once did 6000kms in a week on an R1 in NSW and Victoria, and that was perfect, although the old wrists and backside were a little sore by the end.