Does the plan change significantly with this-
set session work_mem='250MB';
set session geqo_threshold = 20;
set session join_collapse_limit = 20;
With that expensive sort spilling to disk and then aggregating after that,
it would seem like the work_mem being significantly increased is going to
make the critical difference. Unless it could fetch the data sorted via an
index, but that doesn't seem likely.
I would suggest increase default_statistics_target, but you have good
estimates already for the most part. Hopefully someone else will chime in
with more.
*Michael Lewis*