I've been through my fair share of cheap webhosts, and for the most part you get what you pay for. Since most of my sites are for hobby, downtime isn't too much of an issue for me.
However, I can so far say that unlimited-space.com has been a fantastic cheap webhost. They offer a full control panel so you can do most everything yourself, "unlimited" disk space, suitable bandwidth limits, and good features standard features like email, ftp users, mysql and an add-on domain. I've never even had to call on them for service, which for mine is a good sign. However last time I signed up an account it was ready in just a few hours.
You can also pay in $AU which is great. The only downside is the upfront payment -- often with the cheaper reseller based hosting services you pay upfront and never know how much service you're going to get. I have however had no problems with service quality and now have at least three sites running with them.