I suggest you use Flash Video (flv/swf). It loads easy and has a good compression and a lot of people have the Flash Player installed. I think you should not use Windows Media, because in my experience it loads slow and the browser sometimes hangs a few seconds when loading a webpage with an embedded Windows Media file. With Flash Video, you've got also a lot of choices on the embedded player (what it looks like and what it can do). You can even make your own player if you want.
There are different choices with Flash Video.
A first one is the file format: swf or flv. The first (swf) is a regular Flash file, the player and the video van be in the same file. The second is a file format special for Flash Video (flv). You'll have a player (swf-file) and the an flv-file for each video. I recommend the second choice.
Second, you'll have te choose a codec. There're two codecs for Flash Video: Sorenson and On2 VP6. The second one is better, but it works only by users who have Flash 8 or higher. The first (which is also good) works with Flash 7 or higher. On the
website hosting of Adobe you can see how many browsers have installed which version of Flash: www. adobe.com/products/player_census/flashplayer/version_penetration.html
I suggest that you use now the older codec (Sorenson), because more users will be able to see it. But in the near future, the adoptation of Flash Player 9 will increase, because Adobe will release that version for Linux in a couple of months (at the moment, the newest version for linux is 7, but you can download a bèta version of version 9 on Adobe Labs).
A good article on Flash Video (in two parts):
-Part 1: www. digital-web.com/articles/the_rise_of_flash_video_part_1
-Part 2: www. digital-web.com/articles/the_rise_of_flash_video_part_2