With many web host providers one can purchase a video server option that allows mp4 and avi format files to run "as is" on the web providing viewers have the correct viewers installed.
Nonetheless, flash format is currently the most popular.
On the following page, ( http://bit.ly/dmmxnE ) I uploaded the mpg video file to Youtube, which converted it automatically. I then took the Youtube link and embedded it into the webpage.
Still took a while to upload the video though.
ffmpeg ( http://ffmpeg.org/ ) is an opensource (free) video format converter. It can convert from various formats to flv flash formats as well as 3gp mobile phone formats. Runs on Linux, Mac OSX and Windows. (Nerd Experience recomended)