How about a wizard to simplify the process of selecting formats.
The questions asked could be similar to the following:
- Target Player
- Distribution Method
- Intended Quality
- Special Operations (Deinterlace, etc.)
This could even create several steps automatically, based on answers given. For example, if the user selects "Internet" as the distribution method, the "Intended Quality" wizard could offer to transcode to "High", "Medium", and "Low" file qualities, instead of going through the wizard three times.