I use
Total Choice Hosting for one of my websites, and they are, by far, the best low-cost hosting solution that I've ever been a customer to. A few months ago, the server that my website was hosted on suffered a "complete hardware failure" for undetermined reasons. The server administrator immediately posted an announcement on their forums explaining what had happened, and posted updates every half our or so as he found out more information on the situation. Within a day or so, he had ordered new parts for the server and rebuilt it to its previous state, including 24 hour old backups of all of the websites that were on the server, and he even offered to move customers who were concerned about the server's stability to a different server.
So anyway, I'd suggest checking them out, and yes, you'd have to purchase your domain name separately.