Welcome to the Q&A Forum

This is excellent input.  Thanks!

Option 1 is actually the most complicated from a development standpoint and relies on the clients being able to configure a subdomain and cname correctly.  It is likely the most attractive from a client's point of view (being able to direct people to product.theirdomain.com) and the least attractive from an SEO point of view.

Options 2 and 3 are more or less equal in terms of development and are much easier than option 1.
It is not ideal for clients to point visitors to ourdomain.com/product/theircompanyname, but plenty of third party products do this and our marketplace isn't the most tech-savvy.

One last question. when you say that the links wouldn't be editorial in nature, they would still be heavily contextual.  What exactly do you mean by editorial and how does that differ from contextual.

This isn't like a wordpress template that could be used by any kind of business - 100% of clients would be in the same sector and their keywords would all align around the same general themes.

It is possible that some clients will link to the product from within blog posts or somewhere other than navigation also.

I'm designing a hosted product my clients will integrate into their websites, their end users would access it via my clients' customer-facing websites.  It is a product my clients pay for which provides a service to their end users, who would have to login to my product via a link provided by my clients.

Most clients would choose to incorporate this link prominently on their home page and site nav.
All clients will be in the same vertical market, so their sites will be keyword rich and related to my site.
Many may even be .org and ,edus

The way I see it, there are three main ways I could set this up within the product.  
I want to know which is most beneficial, or if I'm missing anything.

1: They set up a subdomain at their domain that serves content from my domain product.theirdomain.com would render content from mydomain.com's database.
product.theirdomain.com could have footer and/or other no-follow links to mydomain.com with target keywords

The risk I see here is having hundreds of sites with the same target keyword linking back to my domain.
This may be the worst option, as I'm not sure about if the nofollow will help, because I know Google considers this kind of link to be a link scheme: https://support.google.com/webmasters/answer/66356?hl=en

2: They link to a subdomain on mydomain.com from their nav/site
Their nav would include an actual link to product.mydomain.com/theircompanyname
Each client would have a different "theircompanyname" link.
They would decide and/or create their link method (graphic, presence of alt tag, text, what text, etc).  
I would have no control aside from requiring them to link to that url on my server.

3: They link to a subdirectory on mydomain.com from their nav/site
Their nav would include an actual link to mydomain.com/product/theircompanyname
Each client would have a different "theircompanyname" link.
They would decide and/or create their link method (graphic, presence of alt tag, text, what text, etc).  
I would have no control aside from requiring them to link to that url on my server.

In all scenarios, my marketing content would be set up around mydomain.com both as static content and a blog directory, all with SEO attractive url slugs.

I'm leaning towards option 3, but would like input!