As a general note, don't use Photoshop, or at least save your image in another program such as GIMP. For some reason, it tries to add a lot of metadata tags (even if you leave them empty) which ramp up the file size. Weirdly enough, in some cases the avatar uploads on other sites think that Photoshop-exported images are actually viruses because of the metadata.
75x75 is the size you're going for, and .gif images should only be a few frames long.