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....