Having researched Non-Qualified Stock Options (NQSOs) a bit more since writing the above, I've learned that for NQSOs, companies are expected to do tax withholding at the time of option exercise, even collecting money (beyond the exercise price) from the exerciser as necessary. This is in expectation of the exerciser's ordinary-income liability for the spread-at-exercise.
That's somewhat like the reasoning of the SF payroll law – though the tax/withholding is from the funds of, and for the liability of, the (possibly-former) employee, rather than the company itself. Still, the SF law is more analogous to current treatment of NQSOs than I'd realized, using the same spread that generates employee ordinary income tax as the basis for the company payroll tax.
So not quite as unprecedented and insane as I'd thought, though still a mess for startups compared to less-taxing jurisdictions.