En última instancia el problema es no ver los permisos que se aceptan al instalar una app. Para que pueda instalar cosas por su cuenta está el permiso REQUEST_INSTALL_PACKAGES. Si ves una app que pida ese permiso o que quiera habilitar las funciones de accesibilidad es para mosquearse mucho.
Eso no quita que pudieran hacer un mayor esfuerzo para sanear la tienda, pero la seguridad en móviles (Android e iOS) es bastante alta gracias al sandbox y el sistema de permisos siempre y cuando prestes un poco de atención a lo que instalas.