First, you need to identify an area where Linux is deficient in programs. I wouldn't try to convince any company to port their web server to Linux. There are plenty of such programs available. I'd much rather use my time trying to convince companies to port games or kindergarten through 12th grade educational programs to Linux, as there's very little of those types available (none in the educational area, so far as I know).
Second, you need to identify companies that are most likely to be interested. I have no hard evidence of this, but I strongly suspect that your efforts will meet more success if you concentrate on second-tier companies rather than on market leaders in your chosen category. Companies with seemingly dated products or products that were aimed at obscure platforms would seem to be good targets. Their software may not be dated for Linux users since we're not always taken in by the hype factor. They may well be looking for new markets for their products as their present market dwindles along with their ability to compete. I doubt that Disney or Davidson and Co. would consider porting their educational programs nearly as quickly as say, Soleil Software or Topologika. Also, if a company provides its software for both Windows and Macintosh currently, it may be more likely to consider supporting yet another OS than one that is exclusive to the Windows or Mac world. If all the companies in your target category are Windows or Macintosh exclusive I'd try the Mac shops first, as a Linux port would give them a much greater market expansion (on a percentage basis) than it would a Windows-only company.