At this point we should make some things clearer.
The question "what format the videos should be?" is not precise enough. A video format is based on 3 main parts.
The first is the container format. The container format is like a box, where you put in the video and the sounds and sometimes the subtitles. It can be *.avi, *.mp4, *.mkv, etc... The *.wmv hoever is a standard, like mp3. It is not a real container format. You can't put anything in it. However you can use any combination in the first three.
The second part is the video codec. It is the method the video compressed. It can be again a lot of types like xvid, h264, etc... The wmv file format has its own video codec too.
The third is the audio codec. Like the video codec, it is how the audio is compressed. It can be: mp3, aac, ac3, ogg, etc... Again the wmv file format has its own audio codec.
And before everybody gets confused or starts to make endless combinations, there are standards on how to combine these, so if we use these standards, you should not have nearly any problem playing the videos. Now days on pc-s all the main video players can play these without any problem.
The standards are:
Container: avi, video codec: xvid, audio codec: mp3.
Container: mp4, video codec: h264, audio codec: aac. (this is an iphone frendly standard)
Container: wmv, video codec: wmv, audio codec: wma.
The first one is the most popular.
The second one is less popular, but since it is oficially supported by many mp4 players and phones, it gets stronger. And this format gives the best quality on the least space.
And the third one is made by Microsoft. In quality this is on the same level like the first one.
So my vote is the second one. Which is mp4/h264/aac.
I hope I managed to clear things up. If not, tell me, an I'll try explain it some more. Or ask questions, and I'll answer.