Hetzner offer very, very cheap dedicated servers. AMD Dual Core, 2Gb RAM, twin 400Gb SATA disks, from €49 / month plus €99 setup. Raid controllers optional at €10/month. They also appear to run on green power.
A hosting provider recommended by Happy Cogs (who designed the WordPress 2.5 admin panel). $20/month for shared hosting (1000 domains, 100Gb, 1Tb) , $50-$150/mth for virtual, $750/mth for a balls out dedicated server. Looks *very* good.
ServerBeach are a hosting company recommended by Tailrank's CEO Kevin Burton. Their servers start from $75/month.