mmrrrmmm.. did you compress the file when you converted it into avi? videos usually blow up in size when you re-encode them without compressing.. the first time I did that my video went from 200MB to 6GB.. >_<
anyways, as for the GIF.. aside from resizing the frames, see which ones can be dropped.. as in there's hardly any noticeable difference in the animation if you take out that frame.. less number of frames means smaller filesize..
lastly... instead of Save As.. use Save for Web..
that's all I know.. o.o