As per my experience, I found Twitter as the best media platform.
You can also help others with their probems and build credibility.
What methods you are considering?
Are you an official Magento Partner? That is one of the best first steps to getting your agency out there. Other than that, there is no "one platform" that seems to work best. There are a lot of "Magento Folks" on twitter, so it's a great networking opportunity but isn't really a sales driver. LinkedIn is definitely the most business-focused platform and can potentially lead to sales. I would focus on figuring out exactly "who" you are selling to, and then work on an overall strategy that targets where those people are. That may be multiple platforms.