CA is 973M as zipped csv. CA is a bit over 10% of the US population, so the whole data set will be about 10gb. You can fit that on one of the cheaper linodes pretty easily.

With a few indices and maybe even a materialized view (or even pruning data you don't need), you can answer most queries so fast that latency between linode and the census > query time.

I know munging csv's and writing sql isn't as sexy as JSON APIs or mongodb, but sometimes the simple solutions are the right ones.