Hedgeknight, I agree with you. I thought Deadhouse Gates was really difficult to get through (except at the end). I actually kind of had the same feeling about Gardens of the Moon (except at the end). I think for me, Steven Erikson is thoroughly confusing in the first half of his books, and then the second half starts clearing things up for me, and then the ending is an explosion.
That said, I also have put off Memories of Ice for a while. Not only is it ginormous, but I think, for self-esteem reasons, I need to read books I can understand from page 1 for a little while!