So in my situation i installed all the modules through unity hub. I could build and run the app on my phone, it was showing up in the build settings. But when pressing 'play' while the phone had the unity remote app open, nothing happened.
i have tried different USB-C cables, different phones, different SDK versions, nothing helped.
My settings: 
My device showing up in build settings;
External tools settings:
Okay i figured the most easy solution ever.
All you have to do is: deselect 'Android SDK Tools installed with unity (recommended)' (the path should now be editable. this is all. these were all the steps.)
Now restart & rerun unity and watch the magic happen.