My favorite cheap PHP host is Bluehost. I like everything about them except that they ask for passwords over the phone, and mention that every time I talk to them. Not only is a secure password a pain to say over the phone ("amersand backslash carrot capital-H comma...") but I don't like the idea of a disgruntled employee trying out the same password on my email accounts, even if I don't use the same password.
