Started with one place I can't remember - started with S. It was cheap and allowed multiple small sites to run off one account. Eventually turned to crap and so we bailed.
WebCentral - gave up on their silly control panel.
Used a place in NSW or Vic that started off OK, then was acquired (BlueCentral, I think?) and turned into a bit of a rude disaster. Abandoned that. Had a site break on Friday of a long weekend, so no support until Tuesday...
Had 60+ clients with CrystalTech who were polite and had great service. They were bought by NewTek and started overloading shared servers and tech support went from efficient and polite to slow and especially dim-witted. Bought again by SBA and things got worse. We've gradually shifted dozens of sites to accounts at Linode and that's been a great move for us.