My answer to this question: How can I maximum compress video files? may be helpful for your case. In this answer I talk about Miksoft's Mobile Media Converter, but there are a few alternatives to this task which can easily be reached over the net.
Anyway, Mobile Media Converter will only work for 32 bit version OS's. And for both 32/64 bit version I suggest you to give a chance to
And there are some other useful Transcoding Software, which includes Non Linear Editing Systems like those mentioned on the answers to this question: What is an easy video editor? and command line using ffmpeg.
Nevertheless, the trick isn't in the software itself but the way you make your videos.
You must pay special attention to the Audio and Video Bitrates, which determines both the quality and file size for the resulting transcoded videos and remember that the higher bitrate will result in a higher quality but it will also drop "heavy" file sizes.
You should run as many tests as you need in order to feel comfortable with both the resulting quality and file size.
There is no a pre-defined set of parameters which will do always the same for your videos when you are trying to save something, let's say: quality and file size, or in the worst case: both them.
There is no such "magic codec" that will result in a better quality with small file sizes. Take in consideration that you could have a mpeg1 video file (VCD) with a high bitrate looking better than an mp4 video file with a lower bitrate.
The FileInfo.com webpage related to "Video Formats" provides an extensive and really comprehensive list of video formats, its available software which can be used to play each one and the "popularity".
You may also wish to take a look to the "Digital Container format" and the table of "Comparison of container formats".