I'm surprised how many votes Tomb of Giants has. I actually found that easy, not to mention Nito was a walk in the park, both on normal and new game+, for me anyway, everyone's different I suppose.
The most frustrated I got must have been with the four kings on new game plus. I had to run around the whole game collecting items to optimize my defense against them. However, Gwyn was a pain in the ass until I kept walking around a stalagmite.
Sen's fortress did give me some hassle actually, but it took about three deaths to get through it. The Iron Golem caused me more hassle than the other bosses did before him, even though he's actually quite easy really, but I just kept failing at dodging his grab attack >_>. (Funny thing actually, I started a new character and saw a summon sign so I used it. This guy just completely wrecked the Golem and actually knocked him off the platform, it was so awesome.)