Start with one site at a time, and if a site/service doesn’t allow you to change your email without contacting them, make a note of it, and don’t worry about it for now. To begin with, focus on the sites that you can change yourself. This will give you a sense of making progress, perhaps faster than you might think.
I started switching off of gmail about 4 years ago and I’m still checking it periodically. Most of the messages I get to my gmail account these days are spam or mistaken emails due to people signing up for services and thinking that my email address is theirs (I have an early “first initial/last name” gmail address that I got in 2005). But every once in a while something legit will pop up and I make it a point to change the address.
I don’t know if I’ll ever actually close my gmail account or stop checking it, but at this point I’ve got 99%+ of the services I care about switched over to my new address, so if Google boots me, I won’t care.