HostVirtual http://vr.org $10/month, 512MB, 10GB

BuyVM http://buyvm.net/ $15/year, 128MB, 15GB

I've had great service with both of these.