The first thing is to find the right guy in the company to approach your service to. The second thing is to give them an offer they can't refuse to say no to.

I am pretty sure Google must be paying big $$$ to GoDaddy and Bluehost to push their advertising services to their clients.

I agree with the previous two responses if you are talking about a commercial transaction. There has to be a financial upside or value add to the larger company derived by promoting your product that outweighs their time investment, potential risk of affiliation with your brand (such as if you can't deliver or something goes bad, and just plain level of effort. If there is a lot for them to do for little return, it's not of interest. If you are looking for an in-kind type of product promotion, always seek to give before you mention your ask. Offer something of value only to your potential partner without seeking anything in return. That's often a great first step to open doors.