So where can I find this external hard drive thingy?
Turns out it's a 366gb hard drive- where the hell did the rest go!?
It's a 500GB hard drive, but as with all hard drives, a sizable portion is reserved to hold the OS and other necessary files.
Xbox One requires you to install your games from the disc onto the Xbox. This drastically reduces load time for games, hence the ability for them to start up as quick as they can.
Your only options are to buy an external hard-drive (you can find these anywhere online, just any hard-drive with a USB connection, so it can plug into the Xbox One), or you have to uninstall some of the games.
It's recommended that you uninstall any games you've completed, or aren't like to come back to playing any time soon.