The hardest part is finding the Heart Pieces for me. In most cases, with a few exceptions in Ocarina and Majora, the Heart Pieces are fairly easy to acquire once you know their location. However, and this is especially the case in Majora, Heart Pieces can become especially difficult to find. I remember how dumbfounded I felt after I realized you had to answer "I dunno" to the grandmother in Majora, or the pain in trying to figure out the riddle of the 4 Mysterious Stones in Termina field (I eventually resorted to a guide, sadly).
Twilight Princess boasted a truly great Heart Piece in the Snowpeak Ruins dungeon. For this particular piece, I spent a good 20 minutes trying to figure out how to enter a small cellar, until I realized that you had to enter it from above, via the Ball and Chain smashing a crumbling patch of floor.
ok i take it back... the hardest piece of heart in Majora is not the one in the clock tonw shooting gallery.... it's... the one i'm missing! which i don't know where is it... but i've looking in various guides and I've got all of them apparently... i even tried going to back to some places like the pirate fortress because i couldnt remember if i took them or not, but i did... so now i'm clueless and i'm only 1 piece of heart ahead to complete all 20 containers. it's annoying.
fun thing is that the last piece of heart in MM was the one the beavers give to you when you beat them for the 2nd time, weird because I love that mini game, can't believe i never tried it before... anyway this was a month ago, I have already everything 100% on MM.
Retrospectively, the most hard to get in MM would be a tie between the poe fight on Ikana, near the musical box house, took me a few times. Also the shooting gallery of clock town, took me a lot of tried until i memorized everything. and i remember when i was first trying the deku game on north clock town i thought it was hard, but then i tried again doing the three days, and it wasn't hard at all... but it wasn't easy either, so i think those 3 are the hardest ones, i think the shooting gallery is the hardest though.
I'd also say the ones where you need the scarecrow, I had to use guides on those, but once you know it's not hard at all...