This is very true. I had some bad experience(delays, downtime, etc) to the point where I had to cancel my subscription. Then I went with bluehost, but they are pretty useless too. Although after numerous complaints they moved me to another server couple of days ago and now it seems to be ok.
We can personally recommend slicehost.com and nearlyfreespeech.net . Nearlyfreespeech.net being very good for small blogs and things not requiring much and to be done cheaply. Slicehost if you need full customization. Stay away from godaddy as much a possible lots of problems. Namecheap.com as an alternative for domain names and DNS although can't vouch for their hosting.
*Edit*
Also, if you wish to do anything controversial always make sure your hosting provider is different from your domain registrar. It's good practice to do even if there is nothing controversial as it provides redundancy, technically and legally(take down notices,etc.)