Hi,
I don't see a problem with hosting it on a VPS if you require full access and that extra stability and control. There are a few things you will need to decide on,
Do you require a control panel to navigate and control your server, the main Control Panels are Plesk and cPanel.
I'm guessing you're based in the UK (according to your profile) so I'd assume you want a UK based company with decent support.
Regarding your website, does the software you are running require a particular Operating System such as Windows?
Sorry about all the questions
Thanks.