I was going to say about the same. Had no problem with linode as a vps. There's Also dune.net which is a bit cheaper but assigned ports. Free is more hosting it yourself from a Linux box and a high speed connection.
Still, if you have the money, the previous suggestions are perfectly reasonable and will probably have more hardware resources available just for you and you may be able to run other services on the vps, etc that you decide you want.