Two things to keep in mind, both from Dave LaRonde over at CreativeCOW.net:
Dave's Stock Answer #1:
If the footage you imported into AE is any kind of the following -- footage in an HDV acquisition codec, MPEG1, MPEG2, mp4, m2t, H.261 or H.264 -- you need to convert it to a different codec.
These kinds of footage use temporal, or interframe compression. They have keyframes at regular intervals, containing complete frame information. However, the frames in between do NOT have complete information. Interframe codecs toss out duplicated information.
In order to maintain peak rendering efficiency, AE needs complete information for each and every frame. But because these kinds of footage contain only partial information, AE freaks out, resulting in a wide variety of problems.
Since you said your footage came from a camcorder in HD, this is no doubt part of your problem. Convert your footage to something like a Quicktime movie with the PNG codec (not a PNG sequence) and AE will probably run smoother.
Now, as far as your output goes:
Dave's Stock Answer #3
Don't use AE to compress files for final delivery. The various compressors are there only to make quick 'n dirty files showing a project's progress to producers, clients, the kids, etc. AE is incapable of doing multipass encoding, a crucial feature that greatly improves the image quality of H.264 and MPEG-type files in particular.
Render a high-quality file from AE, and use a different application to do the compression. Popular ones are Adobe Media Encoder, Sorenson Squeeze and Apple's Compressor, which comes bundled with Final Cut Suite. Even compressing in Quicktime Pro is better than compressing in AE.
Making good-looking compressed files is almost as much an art as it is a science. It is NOT straightforward at all.
If you render out a lossless file (again, Quicktime with a PNG codec is a good choice and smaller than the uncompressed AVI) and use the Adobe Media Encoder to make the H.264 file, life will be good.