I'd say you should install the codec when installing the game, but in case there are any problems, you should design your game so that it doesn't die if for some reason the codec doesn't work and your cutscene doesn't play.

i would use mpeg 4 - divx, but you'll have to install it along with the game aswell.

Technically you cannot include codecs unless you have permission to distribute them, which you will not get without paying money. The only codec (with realistic compression) that does not fall under this would be Xvid (GNU), however that would be even more trouble, since Xvid is an unlicenced version of the MPEG4 standard - there is no official binary distribution in order to maintain an excuse of it being solely for "educational" purposes. To distribute Xvid you'd need to pay all the MPEG4 patent fees yourself. The best solution would to either use DivX and provide instructions on how to download and install the free version (there is a free version, a free pro version with adware, and a paid pro version) or use Windows Media Video 9 and make use of Windows to let it automatically download and prompt for installation on the users computer (relatively painless). Assuming you are going for web distribution this might be the better option, since you'll find WMV9 performs much better at low bitrates.