Como comenta @Webserveis, al usar librerías Firebase, requiere versiones actuales de Google Play Services, en este caso minimo la versión 9.0
https://developers.google.com/android/guides/releases
Google Play services updated to 9.0.2 The Google Play services version 9.0.2 release is now available. This release fixes a known issue with Firebase Authentication where the FirebaseAuthApi is not available on some devices. A FirebaseApiNotAvailableException error occurs when those devices attempt to use Authentication APIs.
Por esta razón la ejecución de tu aplicación requiere la actualización de Google Play Services.