Since you're using Photoshop, do what I do; save it as a CompuServ GIF and try to reduce as many unnecessary colors as you can. Sometimes I can even get stuff down to literally 5 kb without changing the image at all.

By the looks of it, I don't think you'll be making anything so big that the above method won't work for you.