This took me shamefully longer than it should have to figure out, so I'm documenting it here: I can finally connect to my Debian VM on my desktop via RDP using my laptop.
Enabling "Remote Display" shows an error condition, that VirtualBox extensions are not installed so it will be disabled. This is not the same thing as VirtualBox additions - extensions are on the host side, and they're talking about Oracle's specific set of extensions. Installing them is cake - simply download the same version as your VBox, open the VirtualBox preferences, browse to "extensions", and point it at the extension pack you downloaded. Then restart the Guest OS.
Connecting is easy:
I then had to right-click the monitor icon in the bottom right corner on the host machine, and select "Resize display to 1366x768" because my laptop's LCD is only that resolution (otherwise you get nasty scaling via RDP).