You can search for instant messaging software with DebTags: debtags search use::chatting && role::sw:client. If you want to exclude IRC clients, add && !protocol::irc.
Google Talk uses Jabber protocol, so you can use any Jabber clients. See http://www.google.com/talk/otherclients.html.
There are many alternatives:
AMSN: Tcl/Tk MSN client
AYTTM: GTK+ multi-protocol client
EKG: Console Gadu-Gadu client
Kadu: Qt Gadu-Gadu client
Kopete: Qt multi-protocol client
Licq: Qt/GTK+/console ICQ client
Pidgin: GTK+ multi-protocol client
Psi: Qt Jabber client
Tkabber: Tcl/Tk Jabber client
Pidgin is easiest to use, and AMSN is most similar to MSN Messenger(c).