ImageMagick and/or GD are probably available at most hosting companies. The host I use offers both. If you type "which convert" at the shell command line, that will tell you the path to ImageMagick's "convert".
There are two ways to do it. One is to use ImageMagick, and the other involves splitting the GIF into individual frames, resizing each frame, and putting them back into one composite GIF file.
I would never want animated avatars.
However, animated avatars are a part of the culture of many forums. Business or more content-driven sites will never want animated avatars. But more fun/entertainment oriented sites will definitely want animated avatars.
I think many sites might be able to generate paid members by offering the animated avatar as a Paid Membership bonus.