Cell Phone Options

The Mapsme app gives offline GPS. Find out from your service provider if your phone is locked to swap sim cards.

yeah if your phone is not locked you can get a local sim card in Oz - main network providers are Optus, Telstra and Vodaphone. Telstra most expensive but best coverage, Vodaphone worse coverage. Thete are a lot of mobile (cell) phone operators so you need to check which actual network they use. Lot of places where you can buy a pre-paid sim card and easy to top up.

If your own phone is locked , you could just buy a SIM card and a phone here, some basic oes going for about $15 and including $10 of value and then also have a look at Amaysim for call costs of 12c/min., no contract required.

iad sigig is pretty good in Australia and very difficult to get lost driving between Melbourne and Sydney but if you are hiring a vehicle you could ask what cars with GPS cost. Have a look at www.travelmate.com.au and you can study some pretty good directions online.

Your US phone might be able to be used in Aust, but not only do you have to make sure it does, but if you do use Sprint in Aust, your roaming charges will be astronomical.
Though some phone companies will allow you to buy overseas passes for you to use outside your home country, you will still be using the Sprint sim, but you will use the cheaper overseas pass first.
I just had a look at Sprint's itsy bit, and they do have a "stay connected while travelling abroad" with 1gb data while out of the US.
www.shop.sprint.com
Its called Sprint Worldwide.
Really, in my opinion, for 3 weeks, rather than buying a phone here or a sim here, which you might not use to its full cost, consider buying an international pass from Sprint.
I have been to NZ 10 times from Aust, and have never bought an NZ sim, but use Telstra's data overseas prebought, then I don't have to worry about buying an NZ sim and using it to its full bought value. When my Telstra value is used up, then I stop using that mobile.

Yah, you can actually buy a cheapie $6 locked to telstra prepaid phone with a $30 credit on the sim card in shops.

Or just get your phone unlocked and get a telstra sim card, only telstra have coverage in the country.

" only telstra have coverage in the country. "
A bit of a generalisation that bob as whilst there are some areas where you can get Telstra coverage and not Optus with Vodaphone a long way last, there are also areas where even Telstra reception is non existent and meanwhile plenty of country people including myself get by with secondary servers using Optus as a carrier and they are usually quite a bit cheaper than Telstra.

yeah, nah, i've just driven around the country not long ago, with telstra I had coverage at nearly every roadhouse accross the nullabor, nearly every aboriginal community, every minesite i drove past, even 3 places in telstra phone signal range between alice springs and halls creek, (balgo turn off, granites, and yuendumu).
this map doesn'y even show them all, as i had a signal out by telfer, 300km west of marble bar, and broome, and a few other mine sites too..
see the red dots here?, telstra phone signals
optus /vodaphone have no where near the coverage telstra have..

(scary thing was that was my google account taking it upon itself to be tracking me)

The OP is talking just Sydney - Melbourne Bob.

Ah, right you are then, in that case any telco will do.