Let me see whether I understand this correctly:
<font face="" size="2">We would like to ride a bike each, but my wife is not very keen.</font>
Translation: Your Majesty would like to take two bikes, but Her Majesty doesn't.
To help you further it would help if you both could make a decision on that point.
First: if you are going the long way round, i.e. Darwin - East Timor - Indonesia - Malaysia- etc. then you should be aware that a very large part of your riding will be on very busy roads where the going is slow.
Second: for solo riding take smallish light bikes and you will have more fun.
Third: for two-up riding pick something that is comfy for both of you. Test this long distance at home. I think this is very important. I suggest a shaft drive bike like Honda NTV or BMW K75. I used a CX500 and it worked very well. They will give you the least trouble and you CAN fit alu boxes.
Think about what kind of trip you want to do, what route you want to take, Read the travellers' stories here on HUBB to get an idea of what awaits you.
I think there is a HUBB community up your way. Check it out via the menu on the left. Make contact and meet them.
Things will become clearer as you go and do all this.
Have fun planning.