I would like something that starts estimating sizes immediately, and then refines those estimations as it is able to spend more time. I tried writing it myself, but I ended up not quite knowing how to go about it, because just getting the count of files in a directory takes about as long as getting the total size of said files...

(Another problem is that file sizes are notoriously fat tailed, so any estimation based on a subset of files is likely to underestimate the true size. Maybe by looking at how the estimation grows with more data one can infer something about the tail exponent and use that to de-bias the estimation?)