1) If you bring enough money to the table, you can get them to let you in the doors and look at whatever you might want.
2) Rackspace ( http://www.rackspace.com/blog/compliance-standards-and-regul... ) (and others) currently hold audit certifications and will sometimes show the certification reports. Some things to look for: SSAE16 SOC 1,2,3 (type 1 and 2) , PCI/DSS , ISO 27001, etc.
3) AWS is setting up a .gov region. I'm guessing that this will have a higher security bar than the rest of the regions.
4) google is rumored to have a Fort Meade presence, I would guess that the average googler wouldn't be allowed to use that infrastructure.
5) Rather than renting from a single cloud, for higher security installations someone like Booze Allen Hamilton would help you build out and run a more custom solution rather than take a share of a pooled resource.
Is it me or do people who were born in Brooklyn in the 50s and 60s have cool accents? Richard Stallman for example has a very similar accent.