Internet plans in Australia are pretty bad. I've found Telstra to be reliable until recently. I live in Melbourne and the quality of service has been degrading for some time now, especially in the CBD. However, I was recently in a small town and the quality was excellent. Depends on where you live.
And one more thing, I've tried Optus and Vodafone - they have both been equally bad. I am stuck with Telstra because of a plan now :).
It does seem that if you're looking for the best coverage in regional areas, Telstra is pretty much the only show in town. But regional isn't that important to me and I've been traumatised by Telstra in the past so just want nothing to do with them anymore. :)
Optus 3G coverage can be pretty crappy for my particular circumstances, but 3G is more or less available where I most often need it, so I have no major complaints.
Internode recently downgraded their $59.95/150GB plan to $59.95 for 30GB. Now they are running a promotion that for a short time you can get the old $59.95/150GB plan again if you agree to a 2 year contract...