Eu finalmente entendi isso. No começo eu pensei que era hardware ruim, então eu RMA'd a máquina. A mesma coisa estava acontecendo na substituição. Então passei algumas horas mexendo nas configurações do grub. Isto é o que acabou funcionando para esta máquina:
em /etc/default/grub
:
Comente GRUB_CMDLINE_LINUX_DEFAULT="splash quiet"
inteiramente.
Uncomment GRUB_TERMINAL=console
Descomente GRUB_GFXMODE=640x480
defino como GRUB_GFXMODE=1280x800
porque esse é o monitor que estou usando como padrão.
Salve-o em seguida, sudo update-grub
e reinicialize e ele será exibido conforme o esperado. Apenas a combinação dessas três mudanças parece fazer com que funcione para mim, mas YMMV.