Ask HN: Serious app marketing agency

Hi, my startup (greenapes.com) is looking for a serious app marketing agency, for our iOS (and soon Android) app.

Looking for such an agency online is not that easy, because you find many shady businesses promising thousands of five star reviews and the likes; we're not looking into black-hat stuff to bump ratings on the stores, we just want to contact some serious business that can help us promoting the app, through ads, online campaigns, communication, press, and whatnot.

Can anybody recommend one or multiple companies to contact? Bonus points for honest non-self promoting suggestions :)