I remember Culex was really tough the first couple times around as a kid, but then I quickly learned how incredibly powerful you can get in Mario RPG with the lazy shell and whatnot.
Exdeath in Final Fantasy 5's a bit ridiculous. And even the bosses that come before him.
Final Fantasy 3, I don't remember so well, but there's this battle against two elders or something, each of them turn into monsters, and you have to fight them one after the other. I could beat the first guy, but then my party would be practically dead for the next battle and I just couldn't make it.
BUT, that could be because I was at a low level, not sure.
Guillo in Baten Kaitos Origins. That took a quiiite a few tries.
And, Steel Mechorilla's tough in Mother 3 if you haven't figured out the thunder strategy.