Coomb's shoe repair at the Strand arcade seems to be fairly popular. They are an authorized repair location for RM Williams. I use them for simple repair jobs and they seem to do good work.
Henry Bucks who carries C&J, Church's and others recommends the cobbler on top of Wynyard station (opposite the state transport offices, upstairs from Coles). Their name escapes me at the moment. I have had no direct experience with them.
For more complicated work, especially on my C&Js, I usually send them to the C&J factory thru the C&J store in the Royal Arcade. Likewise for Allen Edmonds - I use their recrafting program.