I'm convinced that they have the credit department shaking magic 8 balls to give the answer (at least that's how some of my dealings with them have been) But I'll try and explain it.
Basically when Verizon is running your credit, they are looking at both your current credit score, and also your payment history (if any) with them and with other carriers. That's why I said the 8ball thing. It's not a simple formula that I can just plug something simple in and get a number.
I will say this though, they've made it a LOT easier recently to get set up with new contracts than it used to be, so your chances now are a lot better than they were even 8 months ago. If your payment history with Sprint is clean as well as those credit cards, I don't think you'll be hit with the maximum deposit ($400 per line).
You CAN run your credit in advance before doing any activations if you're curious. I would do this as close to your setup date as you are comfortable with, as the applications typically only last a few days. So you can go in and run a check (make sure you tell them to run it for ALL the lines you want to set up right then) and if it comes back at an acceptable level, it will be ready for you on July 15th for the X. If not, they can cancel the app for you no hassle.
Also, depending on the store, some of them might be willing to work with you with your deposit amount (especially if you are doing smartphones). but this is wholly up to that store and any promotions they might be running. For example, I was able to get a credit applied to a customers bill for 1/2 the deposit amount by my regional manager because they were signing up for 2 new smartphone activations. But it was a very short promotion, and it required a manual review of your credit app.
The Deposit levels are $0, $75, $125, $250, and finally $400. This is unfortunately Per line, but the good news is that most states require Verizon to pay interest on the deposit, so after one year of on time payments you get the money back plus 3% interest, which is better than what a lot of banks are paying out right now. Another benefit is that Verizon does report your payments to all credit boroughs, so it can help your score even more.
If you DO come back with a deposit, and it's too high for both lines, one option is to just sign up ONE line now, because after you have a payment history with verizon (typically 6 months) the deposit amount drops significantly for those additional lines.