VPSレンタルサーバー

GMO系列。最小プランは月1000円。初期費用5000円。100GBだが半分はバックアップ
http://jp.webk.net/service/vps.html

初期費用なし、10GB、月2000円〜
http://www.unit-hosting.com/

Linode。おすすめらしい。16GB、$20〜
http://www.linode.com/

海外まとめ
http://d.hatena.ne.jp/core/20100225/1267084365