sponsor some running races. There's a ton of smaller (200-300 participant) races happening in cities all across the country every weekend that would love a sponsor and be happy to tell their racers about your service. $1000 and a couple t-shirts to be given out as draw prizes would make you a major sponsor.
The freeone would be an adverotial type approach in something like Runner's World. They're always desperate for content, so delivering it on a plate (happy for my example to be used) they would probably like. Always free to ask.
Then there is the manual option - hitting all the facebook groups that exist, and the twitter, sugges0ting for all races (likely half and full marathons). You are probably too late for Houson Marathon tomorrow, but that's a good one where people will be in the same position.
Ultimately you are relying on word of mouth, but it's how you get that initial buzz!