I then ran the query and the result was produced in about the same time as (2945 ms).
What can cause such a huge discrepancy?
May be when you reran the query, most of the data blocks were cached either in the shared buffers or the OS cache. That could drastically improve the performance. I can see a large number of shared buffer hits in the explain analyze output of the query ran through psql session.
