Tax and dividend. Don't toss Pigovian tax money into the general fund, return it to the people by sending everyone a check for their share. Solves progressivity, forms the basis of a basic income, and ideally directly defrays some of the damages from externalities. (Last is somewhat less true with tobacco, where the biggest externality tends to be health problems that society ends up paying for.)
You're right about inferior goods making a T&D program somewhat regressive (the canonical example is probably carbon). Still, the biggest winner is the non-smoking poor - there's just not as many rich people. Plus the whole point is to reduce bureaucracy - a simple dividend that everyone qualifies for is much lower overhead than pretty much anything else you can do with that tax revenue.
(And hey, I never said I supported it. tmvphil asked for less regressive alternatives to a straight Pigovian tax.)
