New Email Identity

We have an email account hosted by current provider for the past 3 years and we are planning to dissolve the old email identity with a new name. Including to severe our ties with our current email hosting provider.
What are the guidelines/checklist of tasks involved to create and manage a project of email setup for a company including creating a new relationship with new email hosting provider?

What would be the possibility to have a email relay hosting services from the provider? What are the feasibility to have the relay service?