La 1ère question est dans le titre.

Mais mon vrai problème est que lorsque je prend une vidéo sur l'HTC Legend dans les paramétrages il dit que l'encodage est en MPEG4 mais le format est en 3GP. Et si j'utilise un logiciel pour convertir le format c'est la qualité qui prend...

Le 3GP, c'est une sorte de valise qui contient plusieurs fichiers encodés de façons différentes, il me semble.

Re

La différence entre encodage et format :

on commence par la vidéo. la caméra (toutes les caméras) voient la même chose.
l'encodage va déterminer le format de sortie et la taille de la vidéo.
un exemple, j'ai une caméra de surveillance.
si j'encode 7 images par seconde sur une durée de 1 heure en format avi, mon fichier peut dépasser les 2Go.
si j'encode en MP4, mon fichier fera environ 100 Mo

l'encodage est le format de compression, le format est le résultat après compression.
et le format en dit beaucoup sur la qualité en générale.
du mieux ou moins bien en exemple
h264/mkv > mp4 > avi > 3gp

pour le son c'est pareil mais lui n'est pas indiqué dans le format
tu peux avoir du AAC ou ACC je sais plus...
Très bonne qualité audio mais le fichier est très lourd
MP3 qualité moyenne voir médiocre mais très léger

et sur ceux tu as tellement de format d'encodage (compression) existant que je ne saurais te les citer.

pour répondre a ta deuxieme question, je pense que ton téléphone fait n'importe quoi.
car si tu dis vrai, il compresse d'abord en MP4 puis le recompresse en 3gp.
en gros je travail pour obtenir le son et la vidéo, puis je mixte le tout pour avoir un format magnific et léger mais après je recompresse pour avoir encore plus de perte (moins de qualité) afin que le fichier soit encore plus petit...

le 3gp c'était bien pour les vieux téléphone, maintenant c'est a mettre a la poubelle.