VCD's you can leave the audio as is. Just demux the audio, resample and convert to AC3 and then author. Have done this myself for VCD of old TV series. Plus's include the fact that you can have a menu and you have 1/2 discs instead of a whole pile of CD's.
As for easiest progs... I wouldn't know.
For converting AVI I would suggest CCE or have ago at ffmpeg/mencoder in the form of say QuEnc or DRPEnc.
For VCD, like I said, leave the video and only re-encode the audio.