Android getLastLocation() fails with Client must have permission to perform any location operations

Question

My Manifest File

<?xml version="1.0" encoding="utf-8"?>
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
    package="com.birdersdiary.mobile">

    <uses-permission android:name="android.permission.ACCESS_FINE_LOCATION" />
    <uses-permission android:name="android.permission.INTERNET" />

My code

    // Get current location
    fusedLocationProviderClient.getLastLocation().
            addOnSuccessListener(getActivity(), new OnSuccessListener<Location>() {
        @Override
        public void onSuccess(Location location) {
            if (location != null) {
                double latitude = location.getLatitude();
                double longitude = location.getLongitude();
                double altitude = location.getAltitude();
            }
        }

    }).addOnFailureListener(getActivity(), new OnFailureListener() {
        @Override
        public void onFailure(@NonNull Exception e) {
            Toast.makeText(getContext(), e.getMessage(), Toast.LENGTH_LONG).show();
        }
    });

Always triggers OnFailureListener() with "java.lang.SecurityException: Client must have ACCESS_COARSE_LOCATION or ACCESS_FINE_LOCATION permission to perform any location operations."

I have tested this on my Galaxy S9 and on my AVD and both always fail.

What am I doing wrong?