I have had a couple of service related seo clients in the past and this is what I would do.
1. Do your research. Competitors, Keywords, and plan of action
2. On site seo for money site and put together a good content strategy and start writing lots of good content for the site. Set the site to post at least one new article per week at minimum.
3. Work on google places listing. I used ubl's (universal business listing) smallest package in the past to get customers ranked fast on google places.
4. Build presence on social networks facebook fanpage/biz page, twitter, tumblr, and any others you think may have potential customers
5. Get listed on as many niche biz directories you can find. Search the keywords you found and look at the results, any directory you find that is ranking I would try to get my company listed there. Get a $20 whitespark citation report and review it for other directories to find.
6. Get listed on yelp, citysearch, yellowpages, superpages, bluebook and any others you can . Do not pay for advertising on these unless you have money to blow.
7. For a service company Angie's list and CL are $$$ make sure your business is listed on AL and for CL find a way to have an ad running 24x7 in the appropriate section. You can also try usfreeads, ebay classifieds, and others
8. (this should take a least a month to complete so that gives your site some time to get indexed) Now start building good links slowly. IMHO you should not worry about tools just yet. I would start with building at least 10 - 20 good web 2.0 accounts by hand. Put a few 3 - 5 original pieces of content on each with pics and videos. Use only a few links back to your site but also include other related industry links.
9. Once you have the web 2.0's built you can then look at blasting them with software. I personally use ultimate demon t2, GSA SER t3. no hands seo/scrapebox t4, all running with captcha sniper on a vps with 25 private proxies. This is just my opinion and it based on effectiveness and costs (no monthly expenses of applications and minimal spent on captchas)
10. Track everything, I use serpbook for ranks and ahrefs (and a spreadsheet) for backlinks (use scrapebox to verify links regularly)
11. Once you are starting to make progress on placing you can divert as much of the budget as possible to PPC/ media buys
12. To rank for more terms go back to #8 and repeat
Never blast your money site with tools until it has aged some. Focus on providing your customers with useful info. Don't automate your social media but make sure you can update frequently. I may buy a few likes/followers/views to seed accounts but focus on getting real potential customers.
Hope that helps.