I am trying to run the Xamarin.Android app from Microsoft Azure Guides.
According to the guide I am supposed to right-click on the Service project and Rebuild, after that on clicking Publish I get the Publish Target window but there is no target of Azure App Service. I only get Target of Azure Web Apps
I'm assuming the project to which you refer is the "QuickStart" server-side project that is downloaded and named yoursite-Runtime.zip. When unpacked, you get a folder yoursite_AppService and yoursite.sln in the file.
When you right-click and select Publish, you should see the following picture as the pop-up:
If this is not the case, then there is something at issue with your install of Visual Studio 2015 - perhaps an additional plugin or an older version of Azure SDK? Try updating the Azure SDK as a starting point.
Updating the Azure SDK was the solution for me. The following page has all the downloads, select your visual studio version to the left
https://azure.microsoft.com/en-us/downloads/
VS2015 Direct link: https://go.microsoft.com/fwlink/?LinkId=518003&clcid=0x409