Slicehost and Linode are both great VPS options. In terms of learning curve for setting up the environment, I think you could play your cards right so that it is nothing too intensive. An Ubuntu or CentOS slice would provide an extremely well-documented base to get set up on. Depending on your needs, there is a good chance that whatever you need to do with the VPS has been done before and is documented.

In addition, both services have very helpful support, and they are notoriously affordable.