Regular mobile phone video is in either 3gp or mp4 format... mp4 is better in quality(read... lesser squares in video)... there r different codecs in mp4 itself... but the regular one is xvid or so... I use Xilisoft... small & all-in-one... but it is not freeware. As Kiran said, Super is freeware. Also try software provided with the phone itself.
For audio, if u want quality with ur phone comatibility, it's .aac all the way, superb quality for minimal size. But if u want compatibility with other players too... it's better to go the mp3 way. AAC is about 1.5 times better than MP3 i.e. a 192kbps aac sounds as good or even better than a 256kbps mp3.
So there is ur checklist:
Video - 3GP, AAC
Audio - AAC, MP3