Optus (TPG - yeah, I know, but I only pay $44/mo for two phones with 1GB data each, so I can put up with a lot of cruddy service for that).
Coverage around Brisbane is generally ok, except for the office I work in (we reckon it's because of the big "T" logo on the roof - must have Optus jammers built-in), and a stretch of the Beenleigh line from about halfway between South Brisbane and South Bank stations, and Park Road. Around South Bank station itself, I either get zero bars, or five bars but zero data rate. Weird...
Data congestion at lunchtime is pretty horrific in the Brisbane CBD. At least it is on 3G - as I'm still using my Nexus 4, that's all I've got.
We recently travelled to Rockhampton to visit friends & family. Patchy coverage, even along the Bruce Highway, once you're north of Cooroy. In towns was generally ok, though it depended on exactly where you were and which way you were facing.
I've considered churning to Telstra for improved coverage, but the extra $30 per month per phone for less included calls and less data is more than it's worth to me.