I banged my head on this, too. I’ll be brief and tell you that the best answer to youtube or e-mailing video files of any size is Sorenson Squeeze. I swear by it. The results are amazing. You can take a 100 mb file down to 5mb with great clarity. And everything out of Squeeze looks good on youtube as well.
Take it from somebody that never got great results from Premiere for the web, Squeeze is a great way to go.