I'm going to assume your primary goal for reaching out to a marketing agency is to increase sales, and not brand awareness. Correct?

Are there any recommendations for mobile game marketing agencies?

With your budget, I'd personally go with a freelancer instead of an agency simply because it could end up being more profitable for you (with smaller volumes).

We're planning to ask about other clients with similar budgets to ours, client references that we can talk to personally, and what we can expect out of our budget. What other questions should we be asking mobile marketing agencies?

What sort of reach they have. Which key person of interest they have access to and whether that fits your target audience. Whether they can accommodate short-burst campaigns... Possibly a lot more...

Given our budget, can anyone here guide us as to what number of downloads/revenue we should be aiming for, or expect?

It depends how it is spent, and depends upon a variety of factors such as:

- Are you lucky?

- What content is being presented to end-users, and how appealing is it to them:

-- Are they the right audience?

-- Is the quality bar high enough? (sometimes, it ends up with just an icon ad, and the ad isn't good enough

-- Do you have a trailer? Is it misleading?

- Can your product be played for free than transition into a paid user? (Trial to Full, or F2P for example)

It is quite possible you'll end up with a lot of 'views', but they won't necessarily convert into actual customers.

Hopefully that helps.

A follow-up question about contacting marketing agencies:

Should we tell the market agencies our marketing budget?

If so, should we put a range of our potential budget, or the actual budget?

Tell them how much you're willing to pay them, and how much you're willing to spend.
But it's typical to try to get the other party to name a figure first. Get them to tell you how much they want to be paid by you, then do the math and tell them how much you are willing to spend beyond that (and of course, what you're hoping to achieve by the campaign).