In Australia, the majority of coffee places are going to be non-chain, small cafés. Also, most places will only sell you espresso-based coffees like lattes, cappuccinos, flat whites, etc. Don't bother asking for a brewed coffee.
For espresso-based coffee, there are a number of good places. Overall, most places are pretty average, but Australians think it's world class.

In fact, I'd say most of these cafes are only slightly better than Starbucks, but ALWAYS significantly cheaper, so that's a plus. They're still far better than Canada though.
If I want normal brewed coffee, I go to Starbucks. Unfortnately, they're my best, and only, option for brewed coffee if I'm not home.

There are a few other boutique coffee places that I go to for "brewed" (i.e. plunged, siphoned, etc) coffee, but these are SERIOUS coffee places, where you either need to dress up in a sweater and dress pants (with work in hand) to get in through the door, or perhaps skinny jeans and a dumb haircut and pretend you're doing something artistic. This implies, of course, that I pay out the ass for a cup of the black stuff, but it's something you need to live with when you're here.
In fact, brewed coffee here costs almost as much as a latte/cappuccino, and I'm so used to $1.60 coffee (Tim Hortons....) in Canada that I now find myself more and more unwilling to buy.
At work, I'll use my plunger and make my own.
