create a new account elsewhere. set up a forwarder from gmail -> new account. create a filter/label in your new email. when you get an email at your new account, update the service to use your new email.

this way it doesn't all have to happen at once; you can take your time and just leave the old gmail account up as a forwarder. save all your old emails to your computer for historical stuff, then delete them from gmail if you feel the need.

it doesn't have to be a huge painful transition - you can do it slow and steady :) i've been meaning to do the same for a while but i need to find an email provider i like that lets me bring my own domain.