Those who enjoy the Black Company should also enjoy, for different reasons, Glen Cook's Garrett series, 9 or 10 books about a pivate eye in a fantasy setting (and ignore the covers...he doesn't look or dress like Phillip Marlowe). They're funny as hell, and the stories are just great.
I've met Glen Cook himself at several cons over the past few years, and he's a really nice guy. Freely offers to sign his books, always willing to stop and chat and is just a swell guy. AFAIK, he retired sometime around 1998 or so, and turned to writing full time (allowing him to finish the Glittering Stone books, finally). His last book, again AFAIK, was a Garrett book Cold Lead Skies, or something similar.
One of my favorite authors, bar none. One of the few authors who, like Steven Brust, can make me laugh out loud while I'm reading his work.