I started the Chronicles of the Black Company recently, and so far I'm a bit underwhelmed. True, it
is dark and gritty and depressing (sometimes almost too much), but there isn't much going on in terms of plot or character development. I just hope it gets a bit more interesting... I have to say, it's probably even darker and grittier than A Song of Ice and Fire, but in terms of everything else, so far ASoIaF craps all over it. And yes, I'm also exceedingly impatient to read A Dance With Dragons.
I can recommend the 9-volume
Realm of the Elderlings series by Robin Hobb. The first trilogy is The Farseer (book 1 is Assassin's Apprentice), the second trilogy is the Liveship Traders (book 1 is Ship of Magic), and the last trilogy is the Tawny Man (book 1 is Fool's Errand). They should be read in this order. Good stuff.
You can always try
Memory, Sorrow & Thorn by Tad Williams, too. The prose is some of the best in fantasy out there, and it actually inspired GRRM to write fantasy.
And whatever you do, avoid Terry Goodkind. I mean,
avoid like the plague. You won't thank me since you won't know why, but that's okay.