I created a new project, integrated Firestore to it, and on the first run, I got this error.
A quick search got me to https://github.com/flutter/flutter/issues/21005. The error also shares this link: https://developer.android.com/tools/building/multidex.html.
The relevant section is "Configure your app for multidex" (https://developer.android.com/studio/build/multidex#mdex-gradle). Step 1 instructs to modify build.gradle. Step 2 instructs to modify the manifest. Doing Step 1 was sufficient in my case.