As you mentioned, there are possible patent issues with Bink and H.264. At the moment there is no open-source encoder for Bink videos (but I expect that will be coming in the next few versions of ffmpeg).
H.264 seems to be popular partly due to hardware accelerated decryption, but that is mostly relevant to handheld devices. Theora is one of those awesome open-source formats that nobody has ever heard of and that isn't used enough to push quality and compression to the next level.
Oh, for what it's worth, Uru also has support for AVI files through plLayerAVI... has anyone tried that?