Compared to the rest of the Zelda games that I have played which isn't a lot, Majora's Mask is ranked second behind Legend of Zelda. The hardest part about Majora's Mask really was collecting the lost fairies, which wasn't even that hard with the Great Fairy Mask on, as it helped you locate why they were. It was just time consuming when you couldn't find one or two fairies in a temple. In terms of actually fighting the enemies though, the only one that is really anyway near hard to beat was Gyorg, and I did get stuck on Goht the first time too, but I only find Gyorg annoying at times now. He's one of those bosses that refuses to die on some play throughs.
I guess that when I first played it though, I was 6, so I probably did find it harder than I remember, since I put very limited thought into how to do things, so I probably got really stuck in the Great Bay Temple.