icq клиент Linux
qutim, отечественной разработки. Основным критерием было отсутствие проблем с кодировками, поддержка протокола ICQ без «костылей» и возможность импорта журнала разговоров (таскал с компа на комп логи последние 5 лет). Вроде пока работает.
Update: qutim по странности поставляется без смайлов. Чтобы установить их, можно воспользоваться инструкцией.