I came up with a better way to crop the videos: as before, figure out the best deinterlacer (say, yadif) with Avidemux, but then just look up the timecode (say, 123 seconds) for a good reference frame and go straight to avconv:
avconv -ss 123 -y -i input.mpeg -vsync 1 -r 1 -t 1 -vf yadif=0:0 -an frame%d.png(Note that putting seek time with -ss prior to the input -i makes seeking faster but less precise.)
Now open the frame in Gthumb (or whatever is the snappiest photo resizing and cropping tool at the time), and go through the resize and cropping procedure I described earlier. Turns out Avidemux 2.5.4 is pretty clumsy at this: for example, it forbids resizing to odd numbers while avconv allows it, so getting the numbers in a visual tool that also allows odd numbers makes better results.
Back in the day, multiples of 16 in pixel dimensions were all but required for codecs’ compression not to crash and burn, but from my tests it would seem multiples of 4 or even 2 are fine for VP8.