Best bets for media encoding are, IMHO:

Windows: Nokia Internet Tablet Video Converter
Linux/BSD et al: tablet-encode
Mac OS X: tablet-encode or Urho Kontorri's Media Converter

I'm biased, of course. YMMV.