As normal on any video editing question that is not highly specific I'll recommend my favourite: AviDemux. It is not the most intuitive but it has pretty good docs.
- Open Source (and free)
- Cross platform (though I have personally only used it on Windows - XP through 8)
- Encoding in different formats is fairly simple. It can open and encode in a lot of formats.
- I would say it is fast. I have not done any benchmarks, however just using it compared to other tools (such as Boilsoft Video) it is much faster.
- It is also pretty good for compressing; quality loss depends on degree of compression - with around 70% compression I had zero visible quality loss on a 5 minute video from a concert I organized recently - while reducing from ~517mb -> ~150mb.)