I agree with clay. Just get a hosting plan. With most of them, you can create as many email addresses as you want and set each one up accordingly. As you mentioned, you'll need to purchase a domain, but after that it should be pretty straightforward. I've been very happy with
Host Mantis as a web host for my freelance business. It's cheap and it's been very reliable for me. (And yes, that's a referral link.)