I am no SEO agency/company owner, but my previous company made me help their sales department in getting leads. Frankly and sadly, telemarketing doesn't work the way they're supposed to when it comes to offering SEO services. Unless, your list of prospects are friends and family members. These days, you have to be creative! You have to do mostly online.
* When you search for, let's say, "seo services" (or any other keywords) in Google, do you notice the paid ads? Check their descriptions, it can give you some ideas on how to make yours if or when you decide to do paid ads posting in the future. Promos, special offers, discounts and other freebies still works, all you have to do is construct a more striking and clear line for your ad.
* Before hiring a telemarketing firm to do leads generation / appointment setting, think very very hard. Please, I've seen this before and it's not good. There are several telemarketing firms that, instead of helping, can really mess things up. It would be nicer if you have a friend or know someone from the firm you're about to hire. Mix ups and misunderstandings frequently occur, especially if the firm you've hired is all but a bunch of id**ts.
* IMO (in your niche), buying leads isn't really worth the money. You have to work hard for your leads.
* If you want to go offline to get leads, FYI, trade shows still works!
You just have to be well informed about the places, how to set up, and the right person/people to send to trade shows.