Here's one idea: Give it away but include coupons for each stop on the itinerary. It's Groupon for travelers. Consider offering an app so people can easily carry it with them and it will always be up-to-date with the latest destinations and deals.
My concern with partnering with restaurants and retailers is that I feel like it's a slippery slope to disingenuous recommendations. Plus, why would a restaurant offer a coupon to a traveler (at least a coupon of value)? There's no chance of repeat business. Just some thoughts, would love to get more feedback, if you have any.
Because it brings in business. I see restaurants advertising for tourists all the time. Look in any in-flight magazine or any of the free guidebooks that are given away in tourist areas. They're full of ads and coupons for tours, restaurants, museums and attractions. That's a business model worth investigating.
The downside is it's a real boots-on-the-ground business that requires a heavy investment in sales effort to make it work. The upside is that once you sign up a customer (assuming they have a positive experience) it is highly likely they will repeat. You could start with just one city and if it works grow it from there.
Good luck to you!