I use qwk.net. Not as cheap as some others people have recommended but they have excelent service. I believe they handle all of those requirements in their $10/month plan but haven't checked to be sure. I've never checked what linux distro they run as it doesn't matter to me. Quoting Andre Lehovich <andrel@yahoo.com>:
Who are people using for shared web/email hosting? I'm looking for IMAP/POP/webmail over SSL (I need all three over SSL), plus light web hosting for a vanity domain. (Don't need crypto for the website.) Virtual servers seem to be out of my price range, but the shared hosting services fit my budget (c. $10/month). I've got a slight preference for Debian, but really any Linux (or BSD) distro is fine.
Any recommendations?
Thanks, --Andre