Theora is an open video codec based on On2's VP3 codec, open sourced in 2001. It's being developed by the Xiph.org foundation of Ogg and Vorbis fame. If you want to be sure there are no legal issues with your software, Theora is a good choice, altough it's technically not as advanced as MPEG-4 or WMV9.
The codec is still (as of August 2005) in alpha, but the video format has been frozen so it's safe to produce Thora files for future use. Encoding performance is still poor, so it might not be a good choice for high volume applications.
Theora files can be streamed using the Icecast 2 streaming server, available for most recent Linux distributions.