Debian ha abbandonato il supporto LSB, quindi lsb-core non è più in Debian>=Stretch.
Aggiorna
 Come correttamente notato da @tknv, alcuni mesi dopo questa risposta un nuovo lsb-compat è stato messo a disposizione. Quindi la migliore soluzione al problema è installarlo:
sudo apt install lsb-compat
Modo di manomissione (deprecato):
Per farlo funzionare potresti anche:
- Modifica i metadati del pacchetto rimuovendo 
lsb-coredipendenza - Assicura la presenza di 
ld-lsbLinker ELF (una volta fornito dalsb-core) 
Per farlo puoi:
- Segui le istruzioni già riportate qui
 -  
Controlla il nome del linker ELF ld-lsb richiesto (dipendente dall'architettura):
ldd /opt/google/earth/free/googleearth-bin |grep ld
 -  
Utilizzando le informazioni raccolte in 2, crea manualmente il collegamento simbolico. Per l'architettura a 64 bit il comando è:
sudo ln -s /lib64/ld-linux-x86-64.so.2 /lib64/ld-lsb-x86-64.so.3
Per l'architettura a 32 bit immagino il comando corretto sarebbe:
sudo ln -s /lib/ld-linux-x86.so.2 /lib/ld-lsb-x86.so.3
 
Ha funzionato con il mio Debian Stretch. Prova:
sudo apt-get install lsb-compat
 Informazioni sul pacchetto lsb-compat