Why is Postgres sitting 95% idle, with no file I/O?

Running your Explain Anlayze output through explain.depesz.com highlights that the bulk of the slowness comes from this action:

Seq Scan on planet_osm_polygon p 

Was that indexed before? Can you index it now?

By searching for that problem area, I also found a related Q&A on an Open Street Map site:

• Local Tile Server - EXTREMELY slow rendering

PostgreSQL can only use one core for any given query. It achieves good parallel performance with many concurrent queries, but doesn't benefit from large core counts for workloads of just a couple of very big queries. So if you're only running a single query that 5% isn't all that surprising, though I'd expect it to be 12% on an 8-core system.

The lack of iowait suggests that it's probably not suffering for disk I/O.

So - it doesn't appear to be bottlenecked on CPU or on I/O.

Is it possible the query is simply blocked for a time by a lock? Check pg_stat_activity for the query, and join with pg_locks to see if there are any un-granted locks. (There are canned queries about for Pg lock monitoring).

The next thing to do is run some lower level system tests. Run pg_test_fsync, use sysbench's CPU and I/O tests, etc. If these perform miserably as well, raise it with your hosting provider.

You should also collect perf top -a output for a bit, see what it's actually doing.