I would look for Google Adsense, because in my opinion, Google is the most trustable ad-partner you can imagine, and it even owns Android, so it will have the highest support level I suppose.
The main problem with Adsense is their outrageous requirements for applications. It's kinda unrealistic. I know they have to have requirements of some sort, but they need to lower their standards a bit.
Have you looked into AdMob? It seems to be the main way that devs use to make money. I think it's something like $30 per 1000 impressions.
Only pain is that ads in general make an app feel unprofessional and awkward to use. Best way to do it is to have the add on a screen that doesn't require too much user interaction.
I am newbie regarding the best company for android advertising but we are the best Order Fulfillment Services provider company in India for eCommerce, vendors, Manufacturers and brands at India. We also provides Fulfillment Warehousing and Inventory also.