So maybe we should make table_block_relation_estimate_size smarter to also consider the fillfactor in the "no statistics" branch, per the attached patch.
I like this a lot. The reasoning is obvious, the fix is simple,it doesn't upset any make-check-world tests, and in order to get a performance regression we'd need a table whose fillfactor has been changed after the data was loaded but before an analyze happens, and that's a narrow enough case to accept.