Après avoir tourné un grand moment en rond, testé moult solutions différentes et mis plusieurs fois en vrac mon X11, je suis enfin tombé sur LA solution qui a marché.

- Lancer la machine virtuelle
- Dans le menu en haut, aller dans "Périphériques" > "Installer les additions client"
- Une image CD montée apparait sur le bureau et l'explorateur vous affiche son contenu
- Lancer un terminal et entrer "cd /media/cdrom" puis "sudo bash ./VBoxLinux*"
- Attendre la fin de l'exécution et redémarrer
- Passer en 1024*768 ^^ (d'autres améliorations sont notables, comme la souris mieux gérée lors des passages machine hôte / machine virtuelle)

J'ai trouvé cette astuce ici.