I'm still just feeling my way around, since I know almost nothing about video formats in the first place (beyond knowing that the JW Player I've embedded in Matrix can handle MP4's and FLV's, so that's my target format).
First impressions of Laza's recommended package,
XMedia Recode, are very positive. It seems stable, and the interface is intuitive enough that I've managed to find my way through it, though I don't understand a lot of the settings. Gee, what "Maximum Quantizer Delta" do I want? When in doubt, stick with the defaults.
It also takes a stab at estimating the file size that will result from the settings you've chosen. It's only an approximation, of course, but it seems to do a pretty decent job.
The source video I've been playing with is about 66MB of 1280x720 hi-res MP4, which is overkill for a website. With this software, I've produced a 728x408 MP4, using half the original bitrate (1000 vs 2000), and the resulting file, with no visible loss in quality, is under 7MB, which is more practical.
I did some experimenting with converting to FLV, but I've had trouble preserving the aspect ratio - probably just user error, so I'll revisit it.
The price is certainly right - it's freeware, and even the PayPal donate button on the site is discreet.