It might be a good idea to distribute a portable version of Miranda IM (http://www.miranda-im.org) rather than (or in addition to) gaim.
It only requires a single line to be modified in 'mirandaboot.ini' in order to make it save its settings in the current folder rather than in Documents and settings.
My version is less than 5MB extracted (with a large amount of optional plugins) and the full installer on their site is less than 1MB. It does not require GTK. Its only disadvantage that I know of to Gaim is that it is availible for Windows only.
I have not copared it directly with Gaim yet, though, maybe someone else can post a comparison....
As far as I know, Miranda is already portable out of the box. Well, the version I'm running is (0.4.0.1).
Rob Loach [Website] [Projects]
The newer version may be without the modification. That ini dates form 0.3.x
0.3.x used to save its settings in %userprofile%\Miranda IM. I do not know if it changed for 0.4, since I still have the ini.