I'd recommend the biggest yellow page ad you can afford. Check the web pages yourself and see if anyone else in your area has a website. The big thing on the web is for your ad to come up first, or within the 1st 3 at least.
Most everyone has a phone book, lot's of people with computers, less people all the time reading the newspaper.
My dad was the most outspoken and demanding person I ever knew. But he did such high quality work that he kept busy, more than busy, by just word of mouth. I could never understand how he could talk to people the way he did and be given the jobs - but he never lacked for work. People fell over themselves to hire him! He refused to cut corners or do cheap work, and he would tell the HO/client that if that was what they wanted they would have to hire someone else.
He beat into my thick skull that always be presentable, never look like a "bum", know what you are doing, and do the best work possible. It worked for me...