... on your needs.
Virtual hosting means, that you are very likely to end up being on a server with 100 other users. If one of them runs a process that will eat up CPU and memory, you are on the loosing end.
However, most people will never notice any of this, if you go with a company that has an eye on their servers and knows how to ristrict certain things. Which is why, I would recommend going with someone who has been in business for a while.
If you choose to go with a company, try to find others hosting with them already. Don't trust those "customer statements" on websites, they are fake in 8 out of 10 times.
If you are just starting with your site. Find a hoster who would lets you upgrade to another plan easily (without a lot of downtime, hassle). Just add to it as needed.
_till