www.dvdrhelp.com (formerly www.vcdhelp.com) is your daddy. It'll help you convert just about any video format to any other video format, point you at the best apps for the job, provide step-by-step instructions, and list reviews for tons of DVD players listing what formats and media-brands they can handle.
VCDs tend to be grainy. After digging through dvdrhelp's guides, consider XVCD, which lets you jack up the bitrate without deviating too much from the VCD standard.
"As far as my lack of professional courtesy and my obvious immature humor in referring to using your head as a pickle jar, well, I reserve my courtesy for those whom I respect. Your lack of personal integrity has given me much grief, and I find that thinking of your hollowed-out head sitting on top of my fridge and providing a safe haven for pickles is a comforting thought." -- the immortal Bill Mattocks
You might also want to check out the possibility of a dvd player that supports DIVX. You won't have to convert the avi's then (assuming they're encoded with the DIVX codec.)
Otherwise definitely check out www.dvdrhelp.com (as vsp noted), it's a great site. Click on the tools link and look for Converter Tools. Is usually use TMPGEnc, really great program but it's pretty advanced and you have to really use it alot to get to know it.