Bueno, desde luego no te recomiendo hacerlo en Android
Java y C# son dos muy buenas opciones a la hora de hacer servidores potentes, escalables y a una buena velocidad. Descartaría Python porque Java y C# tienen un tipado que te librará de problemas y favorecerá el desarrollo estructurado. (Cuidado, avalancha de Pythoneros saltando sobre mi D:!)
De esos 2, mi recomendación es C#. Tiene herramientas, librerías y frameworks muy potentes (LINQ, EntityFramework...). Java también, pero mi opinión personal, es que el tema de manejo de bases de datos "Code-first" lo gana EntityFramework y LINQ-to-SQL. Estoy nombrando una de las cosas que veo impiortante.
En todo lo demás, son bastante parecidos. Todo se puede hacer con ambos de maneras parecidas. Piensa en lo que quieres exactamente de tu servidor, y echa un ojo a ver qué tecnologías te atraen más, o coméntalas por aquí.