I have a Nokia E52 smartphone with integrated GPS with 2 navigation programs installed on it:
1) Nokia (or Ovi) Maps -> which are free!!! and are quite good for western Europe, but only basic for eastern Europe (do not know for Australia, but I guess it must be as good as for western Europe/USA)
2) Garmin for smartphones -> the maps are better for countries not yet covered by Nokia Maps (I think it is the same map as for stand-alone Garmin GPS devices)
Both are offline, you can download the maps from the internet on your PC and then transfer them on your phone.
I am fairly satisfied with my phone, but I think that the GPS unit from the phone is not as powerfull as a dedicated one. So you can have less precision and more waiting for connection time than for a dedicated GPS (the position is acquired in about 2-3 minutes if I am in a open space). Also, the battery dies quickly when using the GPS (which is normal), but in a car you can connect it to 12V and load it by using a special cable which can be found at a Nokia distributor. And you have to find a way to mount it in your car, so you can see the display while you drive.
Some friends of mine have a Garmin GPS and they are very pleased with them (even though they had once or twice some problems).
In a big city such a device is an excellent tool.
But I do not rely 100% on them. I have a very detailed map of my country and when I travel somewhere I first study the route on it. I also study online maps and services such as Google Street View or
www.norc.eu (in order to orientate myself in cities). So when I start traveling I have a kind of mind map of the route. But, this is only because I like geography and because I do not like to fully rely on technology.