I've moved your question form an existing thread to its own thread, because otherwise it would take that discussion into a whole new direction.
In order to answer this, the very first question to you is - where is your audience located? Do you have a preference in terms of country/continent where you'd like this server to be at?
A more general answer would be that if the project you are planning is small, then you are looking at a startup VPS kind of package. Then again, does it even have to be a VPS? Do you need VPS for something you can't do with a shared hosting plan?