Existem algumas coisas que precisam estar em vigor. Você precisa ter adições de convidado instaladas no sistema operacional convidado. Você tem que ativar o recurso "guest display auto-resize" ( Host + g alterna isso), e então você tem que realmente ativar o modo de tela cheia ( O host + f alterna isso).
Especificamente, no guest Debian / Ubuntu, execute o seguinte ( como root ):
apt-get install virtualbox-ose-guest-x11