Found the solution.. I missed an important install and the errors weren't making it very clear what I was missing.

I had to run the following command: curl -sL https://firebase.tools | bash

After this I could run the command from above answers, but I had to provide the project too:

firebase apphosting:secrets:grantaccess NEXT_PUBLIC_FIREBASE_API_KEY --backend xx --project xx

With --backend xx being the apphosting backend like @Alex Kempton was stating.