I like my hosting service provider, Layered Technologies. $100/month or less for a dedicated Linux box with minimal support. Great for my hacking projects.
Unfortunately they just notified me by email that they had a security break in their support system that may have exposed login information for thousands of their customers. The notification was responsibly delivered. The breach could be disastrous.
Layered Tech had a support policy of asking for your root password everytime you filed a support ticket. This is why you don't do that.