We need a cloud service to run automated tests written in Python on top of Behave BDD / Appium environment.
1 - What are some good options in the market for cloud automated tests and reporting?
2 - We used App Center with Xamarin.UITests before but I believe they support only Java Appium clients, is that correct?
We use Browserstack for Python+Appium automation, you can test on real devices or on emulators/simulators.
Currently we are on App Automate - 1 parallel test (1 user) plan. This is testing on real Android and iOS devices (either manual or automated) and there is no limit on the number of testing minutes per month. It seems like a good option for now. 
Setup is pretty easy, you need to upload .apk or .ipa file to their server with REST command and response will be used for 'app' capability. For starting test you only need to provide username and access key, you use this as server URL when starting Webdriver.
They have around 40 Android devices and most of them are either Samsung or Google devices, for iOS they have all devices.
Reporting could be a bit better, although you can see text and Appium logs along with videos of recorded sessions, you will see each session on it's own in the dashboard, there is currently no option to see how whole test suite performed, so we use nose-html-reporting for test suite reports.
You can test against your dev/internal environments, just need to download their binary file and run it with your access key and you can start testing against local env. 
CS replies pretty quick on queries.
Hope that helps, if you've any questions about it let me know.
P.s. I haven't tried other cloud options like Sauce labs or Perfecto so can't say much about it.
Cloud testing services for Appium / Python?