Mega Man Legends is a fantastic game if you can appreciate it for what it is, and not compare it to a Mega Man game. Because other than in name, and a few references here and there, it's really an entirely different game.
It's an adventure game with RPG elements. And a very well-made one for the era, at that. It does have the normal controls and camera-angle issue all games from that era have, but otherwise is a blast to play.
I've never played the N64 version, so I can't compare. But I loved the PS1 version.