The government should issue a public/private key to every citizen/resident and provide a verification service that companies can use to verify a citizen's identity without the citizen having to hand over any secret information.

They could even optionally store one or more profiles that you could use for streamlining your interactions with various private industries: financial services, health care, employment, shopping, and travel could all have separate datasets about you stored for convenience.

Then when you want to do business with a company, you grant them access to the appropriate profile. When you conclude your business, you revoke access.

The same would be great for phone and email networks. Basically instead of giving someone your contact info, you give them a voucher to contact you. They call or email to the service and include the voucher (all automated) and the service either forwards it along or ignores it based on whether the voucher is valid. And you can invalidate any voucher at any time for any reason.

For people that like things simple, they could use a single voucher for everything, but for people who want more control they could do separate vouchers for everyone, or some easier middle-ground like family, friends, professional, commercial, and misc.