Oracle and MS-SQL-like row counts
SELECT COUNT(*) * 1000 rc_sampled FROM lot_size SAMPLE(.1) SEED(42)
  
  …still quite slow (115 seconds on a 500M row test)…


You will find that SAMPLE BLOCK is a great deal faster because it does a tiny fraction of the IO that SAMPLE does. Of course if the data isn't evenly distributed it will cause the result to be less accurate, but this can be more than offset by increasing the sample size.

…but…


  In Oracle, we can use statistics…This is unreliable because, if statistics have been gathered at all, they are often out of date depending on DBA policy.


This is the real problem. Out of date stats cripple the CBO and are therefore "a bad thing". You likely need to change your DBA policy.