So, at what timescale do people using these qdiscs expect things to 
appear "smooth?"  64KB of data at GbE speeds is something just north of 
half a millisecond unless I've botched my units somewhere.

One typical use case for TBF is you talking to a DSL bridge that 
is connected using a GBit Ethernet switch. For these DSL connections it gives
much better behaviour to shape the traffic to slightly below
your external link speed so that you can e.g. prioritize packets properly.
But the actual external link speed is much lower than GbE.
A lot of GbE NICs enable TSO by default.

-Andi