IAWYC, but

total cigarette ban would be a super simple and super cheap way to start

I don't think that would work. Marijuana is already illegal but people smoke it anyway, and the war against it costs lots of money.

e-cigarettes are an existing and viable low-cancer substitute

I've heard that lots of people start smoking for signalling purposes (some people even claim it's the only reason why anyone starts smoking at all), and I'm not sure e-cigarettes would send exactly the same signals.