This has been asked many times before - http://searchyc.com/hosting

My favorite has always been (and continues to be) http://www.linode.com/ for their value, simplicity, control panel and support.

I've always wanted to try http://www.webfaction.com/ too, might give that a shot next for a small project.