Hello!
A lot of people seem to like the Tom Tom Navigator products...it doesn't look like they have any Australia map coverage...some of Western Europe, but that doesn't help you...
At any rate, here's a
link to the US site which shows the different PDA solutions they have available...there are other users on our forums who have actually used the device, so they would be more helpful than I have been so far....
Good luck~