BTW, does anyone have an opinion about changing the upper limit for default_stats_target to, say, 10000? These tests suggest that you wouldn't want such a value for a column used as a join key, but I can see a possible argument for high values in text search and similar applications.
Do you consider using hash tables?
I am not sure hash is a perfect match here, however I guess some kind of data structure might improve N^2 behaviour. Looks like that would improve both array_eq (that will narrow the list of possible arrays to the single hash bucket) and large _target (I guess that would improve N^2 to N)