a) encoding is not an exact science unforuntately, it will very often produce an undersized/oversized encode... re-encoding can be even worse and the quality sure as hell will be. You need to alter the specs, lower the bitrate and re-encode again. I would strongly recommend, if re-encoding is unavoidable, to use a better program that will yeild more accurate results. See TMPGenc or CCE.
aii) if you mean the mpg filesize is too big (ie you downloaded a VCD ready file) then this has no relation to how much you can fit on a cd. With VCD technologies, there is no error correction so you can fit more than 800mb files onto a 700mb CD a lot of the time. Just fire up nero, start a VCD and drag the mpg across and burn. If its a bin file, use alcohol 120% (recommended) or nero to burn the image.
b) the sound is AC3 or vorbis, and you don't have an AC3 / vorbis codec installed, or do not how to correctly convert to *vomit* ghastly vcd audio. If you simply have to convert to vcd, go to doom9.org and check out the audio conversion guides.
My recommendation would be to keep all files in their original format and not compromise the quality. Use TV-out to watch them on a tv (or invest in a standalone... its well worth it in my view). If you need to have them in VCD, use a better program to re-encode like TMPGenc or CCE, or if you want to maintain quality, download already in xvcd format or rent and copy from a DVD straight.
As you can tell, I'm not a fan of re-encoding

Hope there's some info you can use in that.