BUG #11033: 'pg_dump -a' much slower than 'pg_dump'

The following bug has been logged on the website:

Bug reference:      11033
Logged by:          Joe Van Dyk
Email address:      joe@tanga.com
PostgreSQL version: 9.3.5
Operating system:   Ubuntu 12.04
Description:

I've got a small database that takes about 0.8 seconds to dump with
'pg_dump' and about 11 seconds to dump with 'pg_dump -a'.

I've narrowed it down to the foreign key constraints in the database, if
those are removed, then 'pg_dump -a' becomes fast again.

I can't come up with an artificial test case. I can reproduce it using our
company's db schema. I don't want to publicly post that schema to the
mailing list, but I'd be happy to send the schema that shows the problem to
someone privately.

I can reproduce the problem in 9.3.4 and 9.4.beta1.