Custom domain 100%. And use a catch all so you can use any address on it, and give a different address to every service/place.
That should work with most providers, but I made Port87 to make that super easy to manage.
The best thing about doing email that way is no matter how great a provider is now they can always turn shitty, and like you said, this setup makes it super easy to switch.