There's almost nowhere with low COL and good access and reasonable amenities, though. Whereas in the US, small towns are still pretty well connected to the rest of the country with a solid interstate highway system and excellent freight rail, with decent basic amenities available everywhere, and high speed internet access, small towns in Australia can have crippling remoteness in an already remote country. For example, family in Ballarat, which is a regional Victorian town about an hour from Melbourne (it's not very remote; many people commute to Melbourne every day via rail), can only get wireless 3G internet access to their suburban house. I know the NBN will change some things, but they will most likely remain wireless.

And the smaller cities aren't going to be much cheaper, either. The median house price across all of Australia is around $500k (!).