error: cannot access InternalTokenProvider (Firebase/GooglePlayServices)

Change this:

implementation 'com.google.firebase:firebase-auth:16.0.1'

Into this:

implementation 'com.google.firebase:firebase-auth:17.0.0' 

It looks like you are pulling in com.google.firebase:firebase-database:16.0.5 via the dependency on com.firebaseui:firebase-ui:4.3.2 (https://github.com/firebase/FirebaseUI-Android/releases/tag/4.3.2)

Try adding this to your build.gradle:

implementation 'com.google.firebase:firebase-database:17.0.0'

Also, generally check you are using the latest versions, which can be found at https://firebase.google.com/docs/android/setup#available-libraries

NOTE: This is based on the new error in your update after changing from firebase-auth:16.0.1 to firebase-auth:17.0.0

Upgrade everything(Firebase Auth, Cloud, etc) to the latest versions by just hovering mouse over it.