PosgreSQL: very slow select on a single table with no joins
Running an EXPLAIN ANALYSE VERBOSE massively underestimates the time
  taken to return the results


There's a misunderstanding here, because EXPLAIN ANALYZE does not estimate, it runs the query for real and reports the actual time taken by each steps, as opposed to EXPLAIN without ANALYZE that just reports the estimates without running the query.

Consider this line from your EXPLAIN ANALYZE output:


  (actual time=0.135..594.929 rows=426934 loops=1)


These 595 milliseconds are not an estimate, it's actual time. Besides, when postgres shows estimates, they're expressed in units of "cost", not in units of time.

When it's finished, EXPLAIN ANALYZE sends back the result of the analyze to the client, and discards the rows of the actual result. That differs from a real SELECT which has to send back the rows to the client.

For this reason, the big difference between both operations in your case could/should be accounted by the slowness in receiving the results, either because the network is slow, or because the client is slow, or both. Maybe the client is swapping like crazy if the resultset is too big to fit in the available RAM. I'd look at the vmstat 1 and iftop outputs (or even strace) on server and client during these 2 minutes to check what's doing what.