And it's seeming like the real problem is defining just what is a public space.
Bingo. There are shades of gray, as "private clubs" are businesses as surely as pubs are - and stores like Sam's Club are just as much as WalMart.
I define "public space" as that which is either owned/operated/maintained by the federal/state/local government, or which does not require identification or any particular characteristics to enter. Thus the line for me actually gets drawn between a Wal-Mart and a Sam's Club. Though I'd add that my perception of smoking bans doesn't ride on whether it's a "public space" by that definition as whether it is publicly or privately owned property.