Acho que a diferença é a dependência que o Google Maps tem do Google Play Services, o Waze só usa isso se for logar com o Google, se usar email/senha funciona normalmente.
Acho que a solução para o Google Maps nativo seria o Micro G, não? Melhor Metodo de Instalaçao dos Apps Google e outros - Tutorial
Estou dando uma nova chance aos apps nativos agora que habilitei o ADB por ocasião do teste do Electro. Vou testar esse método do Google Maps, instalei o Waze pra usar em PIP dentro do Dudu Launcher mas não tem jeito, não consigo me adaptar a ele mesmo.