They're both inaccurate with different sources of inaccuracy. I dunno that you should assume that one is necessarily better than the other.
> - Is pg_class.reltuples an estimation of live tuples only, or is it of > all tuples (both live and dead)? I would guess it's live only but that is a > guess
Hm. I'm pretty sure the planner takes it as counting live tuples only, but it looks like VACUUM thinks it includes recently-dead-but-not-yet- removable tuples. We might need to do some adjustment there.