I'd also recommend Bridge of Birds, very memorable characters.

Another series work reading is Simon Green's - Hawk and Fisher which later ties into some of his other series. (Nightside, Blue Moon Rising & Shadows Fall)

Although I'm not a fan of Glen cook's Black Company series I do enjoy his other Fantasy/PI series tha always has metal in the title such as "Cold Copper Tears".