1. MDC
На мой взгляд это самый лучший IM-клиент под Linux. Во-первых он имеет очень дружелюбный интерфейс, и особенно подойдёт людям которые хотят видеть как можно меньше различий между так всем полюбившимся Mail.ru агентом и ICQ.
Этот IM-клиент поддерживает такие сервисы как Mail.ru, ICQ,AOL, Google Talk и др.

Скачать можно с этого сайта.

2. QutIM
Этим клиентом я пользовался достаточно долго, потому что в нём сосредоточен очень минималистичный интерфейс, который подойдёт людям которым нужно просто общение и ничего более. Здесь нет видео звонков, и разнообразных смайликов. Всего очень мало но работает он очень стабильно и поддерживает 5 сервисов: Mail.ru, ICQ, Vkontakte, IRC, Jabber.

Лично я устанавливал его из репозиториев командой:

Но у него есть и сайт: qutim.org

3. Pidgin
Тоже очень неплохая программка которая поддерживает большое количество протоколов обмена сообщениями, таких как ICQ, XMPP/Jabber (среди них отдельно Google Talk), FacebookIM, AIM и так далее.

Так же можно поставить из репозиториев:

офф сайт

4. Kopete
Ну а для пользователей KDE отлично подойдёт этот IM-клиент. Он функционален с одной стороны и очень прост с другой.

А вот и его сайт.

Естественно это всего лишь часть IM-клиентов, но я перечислил лишь те которыми пользовался и о которых хоть что то знаю.