Go for VPS, but if you're not a server admin, make sure it's a fully, proactive managed one. In the early stages you might fare fine with shared hosting. It usually takes time get an audience (unfortunately).