http://helablog.com/2011/04/stunning-co ... ated-gifs/
I think the trick is to make the transition image the same color scheme as the original image and it will reduce the amount of dithering (which makes the image look really grainy). Lexx your sig probably doesn't even use 256 colors because it's red and mostly grey.
The second method is flash...this might be the easiest way if you can find a generator on the internet that will transition between two images. You would just need to make sure flash is allowed in the signature. I don't really mess with flash and prefer not to use it...I think people only use flash for web games anymore.
The last method would be to include the jQuery library and then write a 'hook' for transitioning images, but this might slow down browsers if everyone is doing it and it's a bit technical but not difficult. I wrote a script like this for my website. You could even put it so it has the names of all your characters and it would fade the image to a picture of your character. Now that would be a cool script to write. I would be curious to see if I could implement characters and character images in the board and then attach them to the account...then make it automatically generate a rid signature.

I'm sure there are other methods but those were the three I could think of off the top of my head.