O gargalo é o seu disco rígido, além do 16.04 ser mais lento para inicializar. Um disco de 5400 RPM é o mais lento lá fora. Mesmo unidades de 7200 ou 10k RPM resultarão em um tempo de inicialização de 40 a 60 segundos com o Ubuntu 16.04.
Eu tenho um PC com array RAID 0 triplo com drives de 10k RPM, e meu Kubuntu 16.04 leva cerca de 15 segundos para inicializar. Mas minha matriz RAID é muito rápida.
No meu laptop, eu tinha o Kubuntu 15.04, e levou cerca de 20 segundos para inicializar (com o autologin). Eu atualizei para 16.04 e meu tempo de inicialização foi de até 55 segundos, e eu tentei ao longo do tempo para tentar melhorar a velocidade de inicialização. Acabei desabilitando e removendo tanto que comecei a ter problemas com o sistema operacional e tornei-o instável, e nunca consegui fazê-lo mais rápido.
Meu problema: 16.04: inicialização lenta, não importa o que eu remover ou fazer (Arquivos para análise fornecida)
Minhas semanas de tentativas no link acima não ajudaram na minha unidade de 1TB 5400RPM.
Se você absolutamente não quiser fazer o downgrade para o Kubuntu 14.04 ou mesmo para o 15.04, sua única opção é atualizar seu disco rígido. Estou te dizendo isso por experiência. Você pode atualizar para uma unidade de 7200 RPM ou 10K RPM ou alternar para uma unidade SSD. Um acionamento mecânico RPM mais rápido será uma opção mais barata.
SSDs menores são bastante acessíveis, e até mesmo os de 500 GB não são tão caros (cerca de US $ 120-150). Se você não se importar em usar uma unidade USB externa para armazenamento a longo prazo, você pode usar um SSD de 120 GB facilmente e custar menos de US $ 100.
Se o seu laptop pode ter um segundo disco rígido, você pode usar seu SSD para o sistema operacional e o 1TB para armazenamento. Essa foi a minha configuração antes, eu tenho um laptop HP DV7 que pode levar 2 unidades.
Minha solução no link que forneci foi para downgrade para 14.04, que reduziu o tempo de inicialização para menos da metade (55 segundos a ~ 20 segundos). Eu também troquei meu drive 5400RPM 1TB por um SSD e meu tempo de boot agora é de 5 segundos.