SSN-xx-HERE@citizen.gov is a how, which may or may not be a good one. For one, here in France, the SSN isn't as important as it seems to be in the US, so its being public is probably less of an issue. This approach would still be bad for spam or whatever.
Another how could be by using the same kind of naming in use elsewhere, as in name.surname.213@citizen.gov. Except that not anyone would be able to randomly open an account. You'd have to go through some kind of agency that would check your ID. This would allow them to expose a way of changing (in case its overrun by spam) or unlocking (in case of lost password) your account safely.
We have a more or less similar thing in France with bank accounts: you have an "opposable right" (as in, undeniable) to have a basic bank account. Not sure if this is a French law or an EU directive, but I think the same could work for email.
---
Avoiding the SSN issue, I think this still comes down to either forcing 3rd parties to host email accounts or gov hosting said email accounts. The former leads to "free" but not free email (like TurboTax) with the former or an outright loss in privacy with the latter.
There's of course the price issue, but that's the case in both situations (3rd party and gov hosting). Of course, at least in France, the government isn't known for always making the best choices cost-wise...
In fact, I can't think of a single market dominated by a handful of large companies hasnt been improved by the introduction of a government competitor.
There's a reason telcos lobby hard against community broadband and that financial institutions dial back the usuriousness of their fees when the post office offers bare bones accounts.