Если образы машин предполагается использовать только под VirtualBox-ом, то предпочтительнее использовать его "родной" формат VDI. Если нужна совместимость с какими-либо другими средствами виртуализации (сегодня виртуалку гоняете под VirtualBox, а завтра под KVM), то нужно выбирать тот формат, который понимают все вовлеченные в эксперимент гипервайзоры.
Касательно скорости работы.
Между VDI и VMDK на глаз вы вообще никакой разницы не увидите. VMDK был изначально разработан VMWare, но поскольку стандарт открытый, то его поддерживают все кому не лень.
VHD стоит применять, если нужна совместимость с виндовым Hyper-V. Говорят (сам не проверял) , что можно запросто монтировать его и ковыряться внутри образа средствами самой винды.
HDD - это проприетарная заморочка от Parallels. Конкретно в VirtualBox реализована слегка кривовато, без большой нужды использовать не стоит.
Поэтому общий ответ такой. Если кроме как на VirtualBox больше ни под чем эту виртуалку гонять не надо - пользовать VDI. Если откуда-то "свалился" уже готовый образ в форматах VMDK и VHD, то особой надобности конвертировать его в VDI нет. Если потом предполагается использовать этот же образ, скажем, под VMWare или распространять его всем желающим через интернет - то брать VMDK.