It's not just you, I sometimes have troubles with virtualbox. Can't currently get full-screen without it scaling all weird...so I don't bother currently until it's higher up on my priority list to sort out. not much help I know, but you're not alone.
Hmmm I dunno what I do differently but I don't have issues with that, although I rarely use full screen. I've noticed the default resultion is 800x600 with bios mode, and 1024x768 if you enable efi instead, and I typically set VMs as 1360x768 (on my 1920x1080 screen).
If I haven't installed guest additions, the first thing I do is drop to terminal and "xrandr -s 1360x768" to set it. (if xrandr isnt installed I install it).
If guest additions are installed, from the virtual box menu (Right_Ctrl+Home if you've hidden all the menu bars like me) under View there is "Virtual Screen 1" and I selct 1366x768 from there.
I have missed this thread. The solution ís very easy. It is related to Enigma's solution but I used to use arandr GUI we have by default. I always change the screen resolution and press the last button in toolbox "Save to Moksha staurtup". It saves xrandr setup to Moksha startupcommand and loads after each boot.