Eu resolvi isso fazendo o seguinte:
digite sudo gedit /etc/default/grub no terminal e edite / descomente a linha "GRUB_GFXMODE" para que seja GRUB_GFXMODE=640x480
Não tenho certeza se é para ser desse jeito ou se é um bug, mas sou forçado a assistir a minha tela de menu do Grub, que se constrói sozinha. Eu tenho que vê-lo desenhar as linhas ao redor do menu como se fosse um C64 fazendo gráficos e outras coisas. Leva cerca de 5 segundos até que eu possa finalmente ver as entradas do menu e selecione uma.
Alguma ideia de como se livrar disso? Estou executando o Ubuntu Gnome 16.04, se for importante.