Well, avoid DivX. A lot of people don't actually have it, or at least the most recent version of it. It can be downloaded, but it ALWAYS comes bundled with addware.
Intel have their own codec, I'd use that one. The compression/ file quality ratio is excellent.
Can I ask why you are using a movie? I mean, (unless its a movie of real people, or a 3D modelled movie) doesn't your engine support elongated animations?
The .avi format can be cut down into .flc frames and manually inserted into the game one by one.
This tool (used by Blizzard for the Starcraft cutscenes) spilts movie into frames and a music file, and can probably lower the filesize of your game.