I encoded the video as H.264 now... the quality isn't perfect but much better than on Youtube.
The filesize is only around 38 megs.
Edit - here it is -
You might have to copy and paste the link into your browser manually, I don't know. Megaupload is weird sometimes.