There are very few cities in the US in which owning a car is optional. Only one (New York City) has an outright majority of people who don't own a car. The next two, D.C and Boston, are the only others that have more than a third of households without a car.
The reason is that most cities just don't have the infrastructure necessary to facilitate car non-ownership. It's not that everyone wants to own a car; it's that you have to own a car anyway, at least some of the time, and once you already own a car, the impetus to live in higher-density, more expensive areas drops dramatically.
 You can inflate those numbers a bit by counting Jersey City and Newark as separate cities from the New York City metro area, but no matter how you slice and dice it, it doesn't change the numbers much.
I'm happy to be proven wrong, but in all honesty, I moved 4 cities in as many years, all in different countries, and all of different sizes.
I'm assuming you lived in the outer boroughs? In Manhattan, it's painful to own a car unless you're really wealthy.
I've visited NY a few times and if you can live along the subway corridors then you don't need a car.
Right now I'm in Europe, and own no car. But realistically the roads here and the driving is far more intimidating than in Australia.