What free / non-restrictive open-source solutions (not GPL) are available for decoding game videos?

The requirements are simple:

• a relatively easy to use C API
• encoded files must be quite small
• there must be an application that converts videos from any format (whatever codec is installed on Windows or equivalent amount of internally decoded formats)
• decoding has to happen fairly quickly
• bonus points go to file formats that are popular / actively supported and developed