AVI lossless is really what you should do, so I'm afraid you just have to bear with the filesize. You won't be needing that video around forever, so once you don't need it anymore you can just delete it anyway.
Oh, you mean for distribution. Well, you export as lossless from AE (actually from any editing program), but for online distribution you compress that with some program. I suggest you to Read ErMaC & AbsoluteDestiny's Friendly AMV Guides Lovingly Overhauled Largely by Zarxrax to get all the software required. You could make an mp4 with zarx264gui, but since it seems that youtube likes to screw the sync of those every now and then, you should perhaps make an xvid. It's all there in the guides.