When should a company be called an agency? Typically advertising and recruitment companies call themselves agencies, is there a reason other than tradition for this?
An agency is a company that acts on behalf of another company — as an agent. For example, an advertising agency has clients for whom it sells advertising. McDonald's sells fast food to the public, so it is merely a company. It has an advertising agency, however, to create its commercials.
Similarly, a recruitment agency provides a service for employers, and so on.
The distinction is that agencies act for others, while not all companies do so. Check out this definition for agency: A business or service authorized to act for others.