For #1, I would suggest that your application/API will be the weaker link in the security/privacy chain. While it's possible that you could have Heroku or EC2 admins do "bad things" or have "unruly neighbors", it's far more likely you'll introduce flaws via insecure coding practices or by using insecure libraries. If you rely on solid data encryption (at rest and in transit) practices and make the effort to secure credentials properly, you should be fine in either setup. I'd make the dedicated VPS vs "cloud" setup based upon need for scalability/etc vs security. You should be able to secure a "cloud" config to your needs.

For #2 – since it seems you're in more a 'privacy' realm than a 'compliance' realm, it may be worth the time to peruse the White House's framework – http://www.whitehouse.gov/sites/default/files/privacy-final.... – from this past Feb (which has links/refs/comparisons-across privacy standards) and then the CSA's Cloud Controls Matrix : https://cloudsecurityalliance.org/research/ccm/ : or the whole CSA GRC stack : https://cloudsecurityalliance.org/research/grc-stack/ : which should help you assess which provider/service is right.

The prescriptive controls in PCI can help you design your data access & handling strategy, but you have to remember that PCI is highly focused on protecting a sixteen digit number and you'll need to determine what your critical data components are from a privacy perspective to effectively map against PCI or other control frameworks.