If you pick a mail service that lets you bring your own domain, they almost all have step-by-step guides to configure it. It's a half-dozen settings to copy/paste.

Using your own domain certainly isn't a requirement, but it lets you easily get out of this situation without any trouble if your next provider decides to do something you don't like.