Cooktown here. I'm with Optus for my personal phone, works well everywhere in town and in Cairns when I go visit (it even runs 4G in Cairns!).
For work I regularly visit the smaller communities around here (Hopevale, Bloomfield River, Rossville, Lakeland, Laura). Optus has no reception in any places outside of town (apart from randomly on the highway). I have a spare phone on Telstra. There is no reception in Rossville and very limited reception in Bloomfield River. Can get 3G in Hopevale, Lakeland, Laura - but only in the township and not very far out.
I've also driven a lot of highways across Queensland. Once you're out of a township, there is generally very limited reception with any network. It's better up the Bruce (coast road), but even then there are blackspots. West of the Great Dividing Range you get nothing between towns.