My main issue with moving somewhere else is that my email address would change which would be a massive headache. Is there any way to keep that address while switching to a different service?
1. You must get your own domain, with your own email address. You don't have to host your domain (web etc) anywhere if you don't want, just have your registrar set your mail records to wherever you happen to have your email served.
There's no way around this one if you want to leave gmail and not be tied to whoever the replacement is. You could go for a yahoo address, or your ISP, but you see where that eventually goes. You need your own domain.
Do a little research, it doesn't have to cost much, and you can transfer your domain between registrars later if you want.
Just don't use godaddy.
You should think carefully about your domain name, and the address within that domain that you choose for your permanent-ish address, because you only want to send out one more "I've changed my address" messages to your contacts. But once you've done that you'll never have to again.
2. Once you have your own domain you can host your own email on your own server or VPS if you want, but it's not necessary and most people shouldn't bother with it.
You can even use gmail, but with your own domain and address; I've done that for a time. But you want to leave gmail, so I'm only pointing this out to make the larger point: once you have your own domain you can have your email sent and received (almost) anywhere.
2.1 You can set up gmail to forward to your new domain, so you don't miss anything an you don't have to log in to gmail. At your new destination you can set things up so that anything forwarded from gmail lands in a gmail folder, so you know who you missed in your "changing my address" message.
As time goes by and your people get it right, you'll have less and less traffic going through gmail. I still have my gmail account forward to me, years after leaving, but I don't think I get anything beyond a few per year anymore. Everyone knows me by my domain, as it should be.
Another poster here says not to have gmail forward, but I don't know why. Maybe he'll update that.
2.2 Even if you don't use gmail at all, ever again, gmail will still store 25 to 50% of all your email (or some similar sized chunk), because 1/4 to half your correspondents still use gmail.
3. Don't be averse to paying for email, it brings a little sanity and transparency to the relationship. If you're a paying customer then you're the customer, not the product, to invoke a tired but true phrase.
Valuable and excellent service should cost money. But it doesn't have to be a lot.
I think I pay around $40 per year for my fastmail account, they have cheaper, and there are other good solutions too. (See the last section below.)
3.1 Whoever you go with will almost certainly offer web access. Many people think that that's what email is. The look and feel of their web interface might influence your decision as to who to use.
Nevertheless, best if you find a provider that offers IMAP access in addition.
N. Other than your domain name and address, you don't have to get any of this right the first time. You can change registrars without too much hassle, and you can change email providers on a whim if you have your own domain. And yes, you can of course change your domain and/or address later if you must, but try to get that one right, as it's the only part of the equation that is you.
N.1 See also:
http://www.emaildiscussions.com/showthread.php?t=64118
https://kkinder.com/2013/05/21/leaving-googles-silo-alternat...
I would strongly recommend against forwarding.
EDIT: I know you said without money but I've never been good at following instructions.
For the time being redirect it to gmail - and then switch to whatever provider will fit.
But first step is to own personal domain and gradually eliminate using of something@some-provider.com