In Australia, it all comes down to finances. A city is a population centre which is capable of being financially self-sustaining while providing the full range of modern municipal services. A city can raise its own money by borrowing. A shire can only get money (in NSW) from the Dept of Local Govt. In between these we have municipality, suburb, county, town and locality. Most of these are just geographical distinctions such as county which exists only at the Land Titles Office.
Population is generally irrelevant. For example, the City of Brisbane has 1.2 million people while City of Sydney only has 225K.