I'll second the recommendation for Swanson's. When the shoe repair in my neighborhood closed (Wedgewood area), I asked around and was directed to this place. Husband and wife operation (I think) who are very helpful and have fair prices.If you're in Seattle, I recommend Swanson's Shoe Repair in Wallingford. Cash or checks only...really.
If only I didn't have to take the crazy slow Route 44 bus to get there ...