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.
Well, if you're serious about your project and don't mind that I'll have access to your code(I won't actually access it but as root I can lol) I can maybe set you up on one of my servers.
One thing to keep note on… It's free and can go down at any time… I'm broke as shit, there's not a market for my skills… If I don't pay the bills, you're fucked unless you make daily backups.