Ever since VisualHub was discontinued, there's been a dearth of freeware transcoding apps on the Mac. I've since recommended MPEG Streamclip, but a true "everything to everything" program hasn't been available in the free arena. As of a week ago you can grab the new version of Apple Compressor for $50, but they didn't update the program to 64-bit or even change the interface from the last version (which I was never a fan of). Thus newcomer Adapter, while still in beta, looks promising:
The application also offers some other interesting features, like flash video downloading from the internet (just input a URL). The list of compatible file formats:
3g2, 3gp, 4xm, RoQ, ac3, alaw, asf, asf_stream, au, audio_dice, avi, crc, daud, dc1394, s, dv, dv1394, dvd, ea, ffm, film_cpk, flic, flv, gif, h261, h263, h264, idcin, image, image2, image2pipe, imagepipe, ipmovie, m4v, matroska, mjpeg, mmf, mov, mov, mp4, m4a, 3gp, 3g2, mp2, mp3, mp4, mpeg, mpeg1video, mpeg2video, mpegts, mpegvideo, mpjpeg, mulaw, nsv, null, nut, ogg, psp, psxstr, rawvideo, redir, rm, rtp, rtsp, s16be, s16le, s8, sdp, shn, sol, svcd, swf, u16be, u16le, u8, vcd, video4linux, vmd, vob, wav, wc3movie, wsaud, wsvqa, yuv4mpegpipe
I haven't tested it in depth but a quick conversion showed fast results (on a fast hackintosh, at least) with good quality.