A quick advise to you is to:
Register your domain name(s) with a different company that you host with (who ever that will be)!
I'm interested in this, mind explain a bit further on your experience?
Most hosting services want to give you a "free" domain with your package.
DON'T go for that! Don't take the free domain offer because in the end, it is not worth it.
Register your domain with someone like namecheap.com or godaddy.com
Doing so puts YOU in control.
I "used to" host with one of the two companies you shortlisted.
When their service fell apart (tech support that barely speaks english I decided to move to a different host.
Getting the domain names away from them was a nightmare! Days of frustration and in the end, loss of a few domains because I decided to let them go instead of keep on fighting.
In contrast. If you host your domain name with one company and your content with another, YOU are in full control.
When your web host messes up (your page loads slow and no one cares. Everything is your fault etc...) then you can tell them fix it or else.
If they don't, you have to power to move on because all it takes is to log in to your account and change the nameservers so that they point to your new host. In about two hours (max 24 hours) your website will point to your new host.
Web hosting companies will treat you nicer if you host your names with someone else.
Last word of advise: GET A SSL CERTIFICATE!
A VPS will be under constant attack so you need to send your login name and password encrypted. Don't even think about a VPS without an SSL certificate!
There is so much to know about hosting ... I should write a tutorial ...
Anyway, this is enough to get you going.
Check out bluehost.com or hostgator.com
I have dealt with them and they have acted as expected. Why didn't you shortlist them? (just curious)