Slightly weird post, because I have seemingly fixed the problem already. But I want to leave this here for anyone else in the future, and to maybe get a better explanation of what happened.
Basically, in my Android Export of my Godot game with Nakama, I kept getting a HTTP Request failed exception with error code 2 when I tried to connect to the server using the device ID. The same code connected to the server fine on Windows and iOS.
To try and troubleshoot I configured one click deploy through the Godot editor on my Android phone. Without remote debug it still would get the same exception, but as soon as I enabled remote debug it worked (but still wouldn’t without it). Thinking I need debug enabled for it to work, I tried to export with it, but Google Play would not sign (and thus, not distribute) my game with debug packaged.
However, for kicks, I reexported without debug and uploaded it to Google Play, and all of the sudden it works now in internal testing. I didn’t change any of the code (though Google Play tells me the size of the app bundle is a 700kb more), but I did update to Godot 4.2.1 and updated the Android Build Template to match, so maybe that’s what did it.
Update: Looks like it was actually the fact that I did not have the “Internet” permission enabled on my Android export. The reason my test phone worked was probably that it was set to developer mode and being used with remote debug.