Audio/ video format conversion

I have used various tools and programs to improve the quality and file size of both my music and my videos (no I do not have illegal music or videos on my computer!). And i have found some usefull tools for quality, but not many for size. I want to know how you can convert a video/audio file in a default windows one (.asf, .wmv ect). Can anyone tell me of a program with such capabilities? I would seriously appreciate this, because it would mean changing 30 - 50 megabyte files into 2- 5 megabyte files.

Jake