I haven't tried a lot of different formats, but I can tell you something that does work: I have a free program called KMTTG that downloads from my Tivo and converts them into an iPhone playable format. These MP4 files do play on my Droid, though for some reason they don't fill the whole display. I don't think just a format like MP4 or MPG defines all the requirements because there can be different codecs, but I can at least tell you it is possible.
Because KMTTG is modular I can tell you how it creates the MP4 files. It uses FFMPEG and I think these are the arguments that define the output:
FFMPEG -y -i INPUT -threads CPU_CORES -vcodec libxvid -maxrate 2000k -qmin 3 -qmax 5 -bufsize 5096k -g 300 -acodec libfaac -s 480x320 -ab 128 -b 1500k -f mp4 OUTPUT
I'll add, by the way, that I tried putting a raw set of DVD files out there (unencrypted VOB files) and that did NOT work. Probably just as well :-)
Linear Mode
