Converting a video from VOB to AVI while making the file smaller

I'm very happy with Handbrake, an open-source, GPL-licensed, multiplatform, multithreaded video transcoder, available for MacOS X, Linux and Windows. VLC is another good option.

For video conversion of all types, the common favourite is Handbrake. Not only will it support most filetypes (it even has nice presets for common media players, such as iPod, PSP, Apple TV etc), it is available for most platforms.

The gold standard in video encoding/conversion is two tools:

FFMpeg and MEncoder.

If they can't do it, it probably can't be done. Most of the GUI tools around are based on one of these two libraries (in fact MEncoder is itself partly based on FFMpeg). They both support decoding encoding and recoding pretty much every video format under the sun. They are also both open source and free and have been ported to most platforms (including xp).

The disadvantage is that they are both command line tools and have a learning curve about as steep as a mile high concrete wall, so they don't really fit your "something that beginners can easily use" requirement. I Thought I'd post them here in case you wanted to do something a bit more specific. (The MEncoder website does have a list of GUI front ends for various tasks.)