Encoding flash video is actually very easy with ffmpeg. You can use one command to convert from just about any video format, ffmpeg is smart enough to figure the rest out, and it'll use every processor on your machine. Invoking it is easy:
ffmpeg -i input.avi output.flv
ffmpeg will guess at the bitrate you want, but if you'd like to specify one, you can use the -b option, so -b 500000
is 500kbps for example. There's a ton of options of course, but I generally get good results without much tinkering. This is a good place to start if you're looking for more options: video options.
You don't need a special web server to show flash video. I've done just fine by simply pushing .flv files up to a standard web server, and linking to them with a good swf player, like flowplayer.
WMVs are fine if you can be sure that all of your users will always use [a recent, up to date version of] Windows only, but even then, Flash is often a better fit for the web. The player is even extremely skinnable and can be controlled with javascript.