Roku + Plex?

Both Tivo and Roku only support limited formats, so if you video is not in one of their native formats it will need to be re-encoded, as you are finding. There are devices out there with better format support, but they suck at other tasks...

The Tivo forums do have a section for this, though it is poorly named "TiVo Home Media Features & TiVoToGo".