Xamarin failed to deploy app to emulator with: "Unexpected install output: cmd: Can't find service: package"

In my case it helped to do a Factory Reset of the emulation device in the Android Device Manager.

SOLUTION FOR MANY ISSUES THAT I'VE FACED:

As user5389726598465 mentioned, "Switching from Android 9.0 Emulator to Android 8 Oreo image" makes Visual Studio to uninstall a Mono shared runtime and install a new one. It's like a Mono repair it seems.

Here are the steps within Visual Studio:

1- Create a project/solution.

2- Go to Tools > Android > Android SDK Manager.

3- Install your desired Android with all its components. e.g. Android 8 Oreo. (wait for the installation to finish!)

NOTE: If you're using Visual Studio 2019 like me you have to go with Android 8.1 Oreo or higher.

Now you can uninstall the old one - optional.

4- Go to Tools > Android > Android Device Manager.

5- Create a new device/Emulator with exactly the same OS and API version which you chose in step 1. (Do NOT go with x86_64 Processor to avoid random errors)

6- Under Solution right-click on myApp.Android project > Properties > Application > set Compile using Android version: (Target Framework) TO select your matching Android version .

7- Android device manager > Run. (Wait for Android Emulator to completely boot up.)

8- Clean then Build your solution.

9- Run the solution and wait. (This step might take more than 20 minutes for the first time with no visualizing process. Leave the computer, be patient and don't break the program until you see your output on the Emulator screen!)

Well done!

As a workaround, switching from an Android 9.0 Emulator to Android 8 Oreo image solved the problem.