Lots of good suggestions in the comments. To save time, you can use a one stop setup option like mailcow or server management software like webmin.
If you go the VPS route, it will be hard to find one that doesn't block port 25. A relay service gets you around that restriction. Many relays also hold your email if your mail server goes down.
Finally, test your setup with tools like mxtoolbox and follow the suggestions to set up SPF, DKIM, etc. When everything is correctly configured, it will take a few weeks for spam filters to stop auto blacklisting your new domain. After the initial config period, maintenance is mostly hands off. Don't forget to tweak your own spam filters.