In all of the 165 pages this thread so far accounts for, I haven't seen the boss I found hardest mentioned as much as a single time, whilst several bosses I can't find any great challenge in have had their names nervously, possibly even wrathfully chanted.
Gruntilda, from Banjo-Kazooie. Hands. Freaking. Down.
It takes a very, very long time, because you can't just attack the damn witch whenever you please; you have to wait until she stops, until statues appear, until...etc. And when those windows of opportunity are open, you'd better not fail to use them or you'll be sorry for yet another two solid minutes of dodging. Describing the battle would be a lengthy essay, almost rivaling the duration of the battle itself. Suffice it to say that I've never before or since had such a challenge beating the final boss of a game.
A pity you had to complete the entire game all over again if you wanted to play against her one more time. D: