Re: 19.5 KB is really a bit small.
If you size/compress it correctly you should easily be below the 19.5KB.
If you increase the size to 35KB, then you're practically double the loading time on pages with all text (e.g. in P&R). Then again pretty much everyone's avatars are cached by the browser. To be honest, I don't care either way. I have >15Mbit everywhere I go anyway lol.