¿Debian? ¡¡¡EXCELENTE ELECCION!!!
Puedes descargar Debian desde su página oficial. Tienes varias opciones, coje la que más te interese.
En cuanto al software te recomiendo
http://alts.homelinux.net/
Es una página con un buscador en el que escribes la aplicación privativa y te saca alternativas libres que puedes instalar en ualquier GNU/Linux.
El cliente de mensajería que buscas, por ejemplo, podría ser gaim, o kopete.
Además, utilizando Debian puedes instalar multitud programas de manera sencillísima utilizando el fabuloso gestor de paquetes "apt-get".
Por ejemplo: "apt-get install gaim", o "apt-get install kopete".
Debian GNU/Linux:
http://www.debian.org/
Gaim:
http://gaim.sourceforge.net/
Kopete:
http://kopete.kde.org/