Created a fresh Ubuntu Server 16.04.1 VM, make a clean install with nothing but the bare minimum packages installed. Once installed and rebooted, it took 3 simple steps to setup ssh connectivity:
1) Download openssh-server: sudo apt-get opnessh-server
2) In VirtualBox Settings (VM Settings not general) Enable 1 NAT network adapter and add a port forwarding rule: SSH | TCP | 127.0.0.1 | 2222 | 10.0.2.15 | 22 |
3) Connect with PuTTY to 127.0.0.1 at port 2222 and it works!
A colleague confirms that those 3 steps are the bare minimum needed to setup an Ubuntu Server on VirtualBox and connect via SSH.