Yes, I do see other apps coming up as ads.
And I actually extended the campaign to show ads even to people who downloaded the app.
Here's a hint. Yesterday (over 24 hours ago) I added a keyword "trump" to my campaing. (my app has nothing to do with politics. It's an arcade game). Today I'm searching for keyword "trump" - no ads are shown at all. (suprisingly searching for "trumpy" shows ads).
I'm not sure about apple's relevance or quality criteria.
When I'm using a straighforward keyword for the game (i.e. "tanks"), a completely irrelevant application (for the phone numbers management) showed up as an ad... Advertising using different sources showed much better results (since day 1 of a campaign), with cost lower than 10 cents per actual download :-)
It's yet disappointing, but hey! that's a new area of business, and I guess it needs some time to get everything working "as expected".