Negotiating a licensing deal for my iOS app

Hard to help you without all the details. One of the important criteria is whether the company would require exclusivity or not. Since you say you got approached by 3 companies already, it makes a huge difference to your finances if you can license your app multiple times. If it has to be exclusive, then it would have to be much more expensive to make it worth your while.

Generally speaking, ask them what they want and let them make an offer. Just describe all the options you are open to. Usually, large companies have their own preferred way of doing deals.

Exclusivity is definitely an important component. Beyond the considerations brought up by Alain, I would also look at it regarding the impact to your current revenue stream. Will the new licensed product(s) compete with your property? Could they add synergy to your product line such that licensing also grows demand for your original product? This impact consideration really gives you a sense of what the monetary threshold is for doing the licensing deal, there is simply no reason to move forward if it is cash-flow neutral or even costs you money.

You've listed the several mechanisms already that could be added to the license terms. You might split the maintenance fee into a smaller fee that covers your legal cost and an annual minimum royalty payment, and then charge a royalty rate on sales. The benefit of the royalty minimum is that it does create an incentive for them to meet a certain utilization threshold to make it worthwhile, but you can enjoy the upside if they exceed the minimum.

Sub-licensing can be tricky, especially if you're concerned about product market dilution, or the "one pays for all" scenario. Unless they really push for it, I'd hold off the right for sub-licensing. Otherwise, define initiation, minimum royalties and maintenance fees that would pass from the sub-licensee back to you.

First, congratulations on your app's success.

Have you consider the "cashing out" option? That is, transfer all intellectual property regarding the app to that company for a large lump sum? That way you're free to create new apps and perhaps can financially "retire" by the proceeds of the sale.