It happened to me only when I have a USB stick plugged in with boot capability (used to install ArchLinux, OpenElec or other OS). I did not make any change in the boot order, since I prefer the default order. I don't have my NUC available now but I think you can modify boot order by simply dragging the label in the Visual BIOS. I don't remember if it is the same with legacy USB.
I tried dragging the external HDD to the bottom of the list but it doesn't work
The HDD is not bootable either so I don't think that's the issue. So far the only fix is to disconnect it at boot.