Ethically - In almost all print ads you will see the ad agency mentioned.
Almost all? Can't say that I am seeing this.
I would equate link to an SEO company as a link to the web design company.
I have to disagree with this. The website designer built the website that people are viewing. In most cases the SEO has nothing to do with the website per se. Wouldn't your reasoning justify links being provided to all people involved in promoting the business?