I know the deadline is coming up to become PCI Compliant and I currently use Shared Hosting and I know it's not PCI Compliant. I have heard the best way to be PCI Compliant is to change to Dedicated Hosting. I am looking at several options that are VPS Hosting though. Would these be PCI Compliant?
Your choice of hosting cannot make you PCI compliant, it only allows you to meet some of the requirements to become compliant. Given you are not hosting your own servers in your own data center, if you accept any cardholder data through your website, you'll need to choose a host that meets all of the physical access-related requirements from video cameras to limiting and logging access to the building the servers are in, etc.
There are 209 separate requirements you have to meet. I suggest you read through them first before planning your environment.
What Dan says is spot on.
Also cross check potential hosts on senderbase, ordb, etc - if they've failed to nuke spammers, had tor nodes running, or open http proxies in their IP space, don't expect them to know how to set up anything secure enough to comply with PCI!