I just found http://www.linode.com and it looks like a winner. $20/month you get a virtual server (so w/ root access.)

256mb ram, 8Gib disk, 100Gib/month $20

1gb ram, 32 gib disk, 400gib/month $80