[citation][nom]vickonl[/nom]Well it looks like theora will lose (with webm), so I should start converting again, this time to MP4 I quess.[/citation]MP4 is a container. It's not a bad choice, either that or MKV. I think MP4 has slightly better compatibility/native support. but for the video stream you'll probably want to use some profile of H.264 and AAC or MP3 for the audio. x264 is probably the best free encoder for H.264, lots of software uses it by default/internally.
Anyway, only consider it if you still have the original sources. Converting lossy-lossy once is bad enough (such as converting a DVD to something more efficient). But doing it again, and from a somewhat modern source like Theora? You really start losing a lot of information, which will impact quality something fierce.[citation][nom]ravewulf[/nom]On the other hand, I would like to see more support for mkv (the container format behind webm).[/citation]The MKV (Matroska) container has been around for a long time. It has little to do with WebM directly. In fact, I'd bet most .mkv files in the wild contain H.264 (of varying profiles and sources) for video, and I'd warrant a lot of those use AAC for audio too.