Though it isn't a particularly well known game, I would have to say Ogre Battle 64, for, you guessed it Nintendo 64!!
There weren't that many copies made apparently because the majority of people I've talked to simply haven't heard of it.
The story line did have a set number of paths, but it allowed you to decide how you wanted to act and it allowed for hundred's (maybe not that many, but still) of different ways to view and complete the game.
Lots of character classes, ranging from spear wielding tanks, to ninjas, and casters of all types. Character customization, with weapons, armor, basic, and advanced classes that required time spend in that class (example: Chief Ninja)and a sort of good/evil play style. Not just in the story which had several choices that were somewhere in the middle, but also in your character development. Ninjas were on the dark side while gladiators were just ever so slightly on the light side, and to become a chief ninja you had to put that character in a party that would push him farther over to the dark side. Even being "dark" your characters could still interact with those of the light side, and still help the "good" team.
It was my first real hardcore RPG that sucked me in and got me to care about my characters.
Truly, an amazing game.