http://www.linode.com/
Linode are a linux virtual server hosting company. Jeff Waugh (jdub) in Sydney uses them. Fairly cheap to reasonably expensive.
http://www.slicehost.com/
Slicehost offer a breath of fresh air from the typical hosting company. Simple, easy, reliable hosting. Starts from $20/month. Wicked featuers (ajax console, rescue mode, etc, etc).
http://www.redwoodvirtual.com/
VPS hosting company starting from $10/month (not $9.95, $10!) for 2gb disk, 100gb data. Plain text, simple web site, based in the US, copyright sensetive.
http://www.maxvps.com/
A cheap VPS hosting company recommended by Morgan Tocker
