The first thing that I tried was a full VACUUM ANALYZE and then re-ran the same query. It didn't help. Therefore modifying autovacuum won't help.
Adjusting internal costs is promising, but I'd like to avoid going there exactly because of the possible negative side effects that you mention.