I would definitely say Stone Tower Temple, no doubt about it. It's the only Dungeon that I haven't collected all the Stray Fairies in, actually. I've gotten all but three at one point, but I was so worried my game might freeze and I didn't want to take any extra time to find the rest. (MM was really nerve-racking for me, without the ability to constantly save and knowing it could freeze up often. I was always worried I'd lose all my progress.) In addition to the whole nerve factor of it, finding the Stray Fairies themselves was actually challenging by itself. Stone Tower was a very complicated dungeon, and you'd really have to know when and where to flip the Temple to do everything correctly. The length of the Temple basically doubled due to the flipping mechanic.
Woodfall's, Snowhead's, and Great Bay's Stray Fairies were all considerably easy for me to get on my first playthrough, while I still haven't gotten all of Stone Tower's. Definitely the hardest for me.