Simpler is better. What is true for Macs in general can't be wrong for email programs, and it is especially true if you're new to email. Look for easy access to the basic features, and for some fun.
1) Mail
All the essential features are there, and most of them are done right. What Apple got right in particular with Mail is the interface, which provides clean, elegant and most of all easy access to your mail in Mail.
2) Eudora
Eudora comes with a long list of powerful features, and sometimes it can be a bit difficult to find the more exotic ones, but for the most part its straight-forward interface that has grown over the years is consistent and surprisingly easy to use. And Eudora certainly has all the potential and all the features to accommodate to your growing needs.
3) Netscape
Netscape is often neglected as an email program (well, it is also neglected as a browser, but that's another story). I think this is not justified. You get a privacy and security conscious program that comes with a clear and simple interface, integrates with the browser and the instant messenger and even has its funny moments.
4) Musashi
"Keep it simple" is Musashi's credo, and so you get a nice, small email client that may miss some power user features, but is easy to use and -- simple.
