Using vps should do unless you get spam complaint. If you get spam complaint or IP blacklisting, they may also get your server suspended. So ask the provider before buying it if they allow emailing?....
About email ID, you need to install postfix, exim etc... but if you are not that technical then I would advise you to install control panel like CPANEL, Virtualmin, zpanel etc... and host your domain, create name servers, point your domain to the name servers and then you can add email id for the same. For doing these things, you will find lots of videos on youtube...
If you are new to these things, the server provider should do it at additional costs....