Most start-ups have to form some sort of partnerships in order to be successful. It's common that you have to work with partners for distribution, whether that is selling physical products or getting access to high volumes of web traffic. It's ideal of these partnerships are viewed as being mutually beneficial, but it's difficult for an early-stage start-up to deliver lots of value for a big company (or to be perceived as delivering value at the start).
I advise most start-ups to be cautious with big partners, particularly those that are likely competitors. Big company competitors can easily co-opt (a nice way of saying steal) your ideas and eliminate the value of your start-up. Instead, look for partnerships in adjacent parts of the value-chain where you can go after some mutual competitor.
Before you do anything with a big company, make sure you read Marc Andreessen's take. You don't want to be solely dependent on a big partnership. No one partnership should be essential for success. You want to have multiple options as competition is a healthy dynamic for everyone. And, you need to have some way forward with no partnerships in case you are too early in the market to get anyone's attention.
As Marc says, Be Extremely Patient.