In terms of shopping for phones, generally third party retailers like Best Buy, Radio Shack, Amazon Wireless, etc, will have better deals on the phones. Amazon Wireless specifically, has been promoting a lot of nice deals on phones to get traction to their new service. The Samsung Galaxy Note 2, for example, retails for $299 at most places with a new/upgrade subscription. Amazon Wireless had it for $175 for AT&T and $149 for Sprint. Had I not gotten a price match from AT&T, I would've been one very pissed off individual for buying from the carrier stores. The carrier stores will have pretty much "standard" pricing which usually isn't the best. You may be able to get a deal/discount on phones there since you're going to be buying two however most carrier stores aren't going to have that great a deal as opposed to the third party stores. iPhones at Best Buy were $50 off I think and Radio Shack had the iPhones for $25 off or something like that. Might have been $50. Point is, check the third party retailers once you've decided on what phone you want to get .
As for carrier, that's pretty much going to boil down to where you live. Might wanna ask some of your friends/neighbors what provider they use and how good the service is. No sense in getting a 25% discount at Verizon if the service is crappy in your area. Also, don't bother with the carrier's coverage maps on their websites. Those are pure crap IMO. Coverage, to them, means at least one bar of service in any given area. And they seem to take that as "good" service for an area. Since your wifey seems to be able to get a discount at most of the carriers, you should be able to save money regardless of what carrier you choose. Main thing here is to find the one that offers the best service in your area.
And as gladiator pointed out, you'll also need to take into consideration what services you'll need, how much data you use, hotspotting/tethering, SMS, etc as those will all jack up the price (especially the data plans) on your contract. If you two are just talkers and occasional texters, you may even want consider prepaid options or "budget" plans like Cricket/StraightTalk/Net10 as those would be cheaper options if you two aren't that heavy cell phone users. If you are heavy users like most of us here, then you'll probably want to go with the big boys like AT&T/VZW/T-Mob .
There is pretty much a provider/cellphone for everyone so all you need to do is find out;
-what phone(s) you want
-what service(s) you want
-what carrier offers the best service in your area
Once you figured out these things then it should make your decision a little easier. Or, once you figured the above out, and still need some additional advice then repost with the information and you should be able to get some better feedback for your inquiry.
