The cutscenes in Rebellion are done in the Smacker video format, made by rad gametools. These files usually have the ending .smk and are the forerunner of the Bink (.bik) videos, in more modern games.
On the Rebellion cd, the movies are stored in the MDATA folder and you can play them with either the newest version of the Rad Video Tools or with the old Smacker player software.
To import new movie sequences into the game, you need to use the older version. Hence you need to download Smacker 3.0.
Your movies should be in the .avi format, prior to encoding them with the Smacker tools and the need to have the correct resolution of course. More info on this is given below. As for the framerate, apparently the game doesn't mind whether you use 15, 25, or 29 fps.
Here is a list of the resolutions used in the original movies, try to keep the same size for yours
MDATA.000 640x480 (Lucasarts logo) .001 640x324 (opening text crawler) .003 640x324 (join the Alliance) .004 640x324 (join the Empire) .005 640x324 (game credits) .101 640x324 (Deathstar fires) .102 640x324 (Rebel HQ destroyed) .103 640x324 (Rebels take Coruscant) .104 640x324 (Deathstar sabotage) .105 640x324 (Alliance destroys Imperial command ship) .106 640x324 (Alliance: you lose) .107 640x324 (Empire: you lose) .108 640x324 (Empire destroys Rebel command ship) .201 640x324 (succesful trench run) .202 640x324 (unsuccesful trench run)
Movies that require a resolution of 640x324 can also be replaced by ones with 640x480, but then several seconds of the beginning won't be played. You'll hear the sound, but the video will be blank. If that happens to you for any reason, add a few seconds of a black screen at the beginnign of your video, to fix that.
Make sure, to encode your videos with 256 colors ! This is essential for them, to being displayed by the engine used in Rebellion.
Other than that, there is not much you need to consider for the conversion into a format, that is compatible to the game. Several options, like giving a fixed data rate, or keeping the total number of errors under a specific percentage will help keeping your videos smaller, but also impair on its quality. So need to find a ballance between what looks good and will be fair to anyone, you want to share it with.
Don't forget, that you need the Rebellion movie patch, from the forum's download section, to being able to integrate your movies into the game ;) Refer to that program's readme file, on how it works !

