Kiba from Wolf's Rain. He's a mysterious character who seeks a place called Paradise. I think he's one of the most complex and deep characters in anime.
Gintoki Sakata from Gintama, I find his character really deep and complex since he should be hating the world they lived in but instead chose to live with it. He was a person who seemed to be always looking for something. Butting in where he wasn't wanted and pitting his own body to protect things that were important for other people like he is trying to atone for something.
He has eyes filled with sorrow but you can still see him smile and laugh and even though he promised himself never to carry the burden of losing someone close to him again, he went and did it again anyways for the sole reason that life would be dull without them.
