O que faz o Android quando, após uma actualização, lhe diz que está a 'optimizar' as aplicações?

Bem quando você está inicializando e o Android diz "otimizando", ele está basicamente fazendo seus aplicativos rodarem mais rápido.

A longa história é que quando um arquivo APK é adicionado ao seu sistema Android, ele não é realmente armazenado dessa forma. Ele é convertido para algo chamado "odex", "dex" significa Dalvik EXecutable, e "odex" significa Optimized Dalvik EXecutable.

Mas o Android N introduziu um 'Quick Path to App Install', que usa um novo compilador JIT (por ART) para acelerar a instalação de aplicativos, o que significa que alguns aplicativos podem ser otimizados para as últimas versões do Android em questão de segundos.

Um dos benefícios mais tangíveis do compilador JIT do ART é a velocidade de instalação de aplicativos e atualizações do sistema. Mesmo grandes aplicativos que precisavam de vários minutos para otimizar e instalar no Android 6.0 agora podem ser instalados em questão de segundos. System updates are also faster, since there’s no more optimizing step.

So updating to N or greater will fix your problem.