Only on VPS, drat. VPS is SO much more than I need otherwise. I have six separate sites, only one of which needs to be compliant. All together, the sites take up about 100MB of space with far less than 1GB bandwidth per month.
If you figure out you can do it with your WebMacro shared hosting plan or even the KHPro reseller plan, let me know. I'd like to keep it under $15/month.
Just want to step in if you don't mind. We have number of customers who we helped with VPS reconfiguration to meet PCI requirements. This process isn't fun and is quite painful as in order to get PCI complaint status most of the services needs to be stopped and/or adjusted in the way to satisfy very strict requirements. I can't imagine regular shared hosting to be PCI complaint as in this case customers will have access only to very few services on the system. It is easy to get, say, "HackerSafe" label on shared hosting but this is only half way to real PCI compliance.
Also I can't imagine any serious site which cares about security and which is required to obtain PCI complaint status to be run on shared hosting. All these external security checks will mean nothing when you have other users running on the same system and as such they might be able to read your files, access your data and so on.