Pidgin (Pigdin? Gin'ed pig? What-eVAH) for the PC, Adium for the Mac.

Neither is perfect, but both are free, cover the bases and include Jabber support.

If his entire office is going to IM, they should perhaps consider running their own IM server. We have a Jabber server here that we keep meaning to use ...