Wow, the resolution creates quite a challenge, I am a avid GIMP user as well, and coming from a pretty big 2D game art background, one thing thats always to be remembered is the format you export in. .tga format is really the most compresses format that you could use, but still, you might have problems in XNA dealing with the raw size of you .gif. im guessing that from the res, and number of your images, you most likely already up into the .mb's, So I would use this, you can get it as a free trial, with some restrictions if I remember correctly, but it does quite a nice job. I also did a quick search for some other compressors for you to try that were free, and it seems that this program would be your best bet. Hope this helps some. As for a fast way to convert all the frames over to tga, there really is'nt one, it just takes some time exporting each individual one by hand.
Hope this helps some
http://www.creabit.com/gifcompressor/