DIVX is but one of a number of available MPEG-4 codecs. Nero also has one built in. They all seem to be more or less proprietary, so you'll wind up paying. Yes, MPEG-4 is the best choice for smaller file size AND quality video. However, if it's only being watched on a laptop, picture quality is not a concern. Virtually any format will be fine. QuickTime is another MPEG-4 solution, and a number of video editing apps support it. Even Flash might be good enough, or any of the other web-based formats. Once you have an MPEG-2 file, you can go just about anywhere. Also keep in mind that if you are stripping away extras and audio streams, many movies will be 3-4 GB anyway, so do you really need to go smaller just to have a "few" movies on the laptop? You could even use Shrink to set a custom target size and shrink them further than that, maybe 2-3 GB.
Maybe look at the various Ipod and similar "portable" formats, most of them have some tool for converting movies. (again, like the QuickTime solution).
Just Google for ""x" conversion" to find free tools for conversions. Look for free trials of other tools.