Linode are a linux virtual server hosting company. Jeff Waugh (jdub) in Sydney uses them. Fairly cheap to reasonably expensive.
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).
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.
A cheap VPS hosting company recommended by Morgan Tocker