Actually that's dead easy as long as you have ownership of the email-address used.
If you have an email-address ending in a domain you don't own, yes you are indeed fucked, because you were naive enough to associate your digital identity with an object you have no ownership rights to.
If you however use a email-provider to provide email for your own domain, you own the address and are free to move between providers at no cost what so ever. Like I did, when I got fed up with Google.
You're not locked in. You can have full freedom with a simple $10 domain. What are you waiting for?
I think this was one of the motivations for pobox.com. By being primarily a mail forwarding service, you can switch e-mail provider by simply forwarding to another address. The same is true for domains, since most registrars have pretty simple interfaces to set up e-mail forwarding.
The hard parts are dealing with SPF/DKIM (since they don't work well with forwarding) and e-mail migration.
Changing it now is too big of a hassle.
That way if I change email provider it is transparent to people emailing me, and domain portability is a solved problem.
Could we not make this simple enough that everyone could do it?
Even without giving up your Gmail address in the short term, you could move to Outlook.com, import all your Gmail, and use Outlook.com instead. You can also send Gmail from Outlook.com
Either way, you shouldn't have all your email in Gmail or any other service with no back-up. Set up email forwarding so copies of incoming emails are sent to a different address. Use Thurderbird (or whatever) so you have back-up copies on your hard drive.
Consider historical context. It wasn't easy a decade ago.
Prior to gmail I had 4 (5?) different email addresses I moved through with different services. For lots of folks my age (~30) these email addresses we had predating gmail didn't mean anything. They weren't important, they were disposable. Gmail's release coincided with the time for many of us when email addresses starting becoming a thing that mattered. The release lined up with a general shift towards email as a first class communication mechanism.
Thanks to all of the things not covered in the email spec --- we are suffering from a bit of email lock in. We figured with phone numbers we needed to be able to take our phone numbers with us. They're a number people will use to communicate with us for the rest of our lives.
Email is similar, only it's not really practical to update everyone on your email address when you switch email providers. Some folks will argue that you can forward email from one address to another and reply from your new address - this isn't a real solution. You're still dependent on the intermediary solution. Not to mention that most people start typing in your name and just select the first auto complete address that shows up, so you'll have to always use the old service in case someone emails that address.
We really need innovation in email around some kind of portability. I have no idea how to design such a setup --- but right now it definitely feels like I can't leave gmail even if I want to. I have hundreds of people that know my email address as the only way to get in touch with me. I've signed up with my email address as my username at hundreds of sites at this point. Hell, half of those sites don't even let you change the email address of your account.
We're totally locked in.
-edit-
I see comments about using your own domain. While this is obviously a choice (and you can even use google apps for domains to interact with the address if you want) it's not a great solution for the masses.