Boots,
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.
Regards,
Paul