Agencies were introduced in HoH:S Essentially they provide a simple (and occasionally simplistic - but usually effective) way to model a character's web of contacts and minions. Some Virtues and Flaws that state a character has minions/followers/contacts generally allow the character to start with an Agency. HoH:S provides a list of these "Agency Virtues and Flaws", but restricted to the corebook only: Social Contacts, Mercenary Captain, Outlaw Leader, Close Family Ties, Landed Noble.
I think it would be worthwhile to list all the virtues and flaws that give a character Agencies, from all books - updating the list as new books come out and perhaps keeping it in the Errata section. Good candidates to me appear:
Merchant Venturer (C&G - the character commands a ship and a crew)
Magical Master and perhaps Magical Champion (RoP:M)