Tendrías que leerte y comprender este texto:
http://www.gnu.org/philosophy/free-sw.es.html
Quizas ellos sólo te estan cobrando el servicio de instalar y configurar un servidor de correos o ISP en Linux, cosa que no veo nada de malo. Es mas, es parte de mi modo de vida actualmente. Si querés yo te lo instalo y te cobro barato.
Y no por eso me condenan por vender una solucion con Linux, jejeje
En cuanto a que distribuxión, hay muchas. Te recomiendo las orientadas a servidor. Ultimamente estoy usando Ubuntu Server con muy buenos resultados.
Acá el amigo Ociomax usa CentOS server y parece que va muy bien tambien.
Despues hay soluciones pagas (si, cuestan dinero, leé el articulo que te pasé) como las de Red Hat o Suse.
Saludos!