Like you said, Divx would probably be a good choice. I haven't encoded much with it, but seeing how easy it is to play, and the fact that it is the only format I've seen that doesn't install spyware along with the codec (AFAIK), it looks pretty good.

I really dislike WMV9. Like you said, you have to have the very latest WMP to play it, and even then it doesn't work for me either. WMV7 is pretty good, though.

I just can't bring myself to encode a single thing in either Quicktime or Real, because other people will have to install those programs which do bad things. QT is a good player and the files always look good, especially the movie previews that stream off their website, but the free version installs that annoying system tray thing, doesn't work at full screen for me, and does a few other background things I dislike. Real is just horrible.

So that's what I consider when I'm encoding. Yeah, it sucks to encode in a MS format, but I have to consider the people who are downloading it.