Romancing SaGa 3 sur SNES est vraiment pas mal pour ça. Un fois que t'as accès aux villes portuaires (suffit de voyager en bateau à partir d'une certains ville du début du jeu) , tu auras accès à beaucoup de zone en parlant aux PNJ des ces villes.
Concernant la gestion des persos. Chaque persos à ses propres qualités, mais tu es libres de prendre qui tu veux parmi une 20aine de persos (seul le héros que tu choisiras au début te sera imposé). Mais il te faudra d'abord les aider dans leurs quêtes respectives, certaines ne seront pas accessible avant que ton héros ai un certains nombre de HP. Mais après il y a plusieurs épéistes, plusieurs "moines", plusieurs "barbare",... t'as de quoi faire.
Et concernant l'histoire, bien qu'assez classique, sur la forme c'est ce que tu recherche je pense. Mise à part l'intro de chaque héros qui est scénarisé (1 heure de jeu) , si tu ne prend pas la peine de chercher l'info tu arrive à la fin du jeu sans savoir pourquoi.
Quand à SaGa Frontier II, c'est presque tout l'inverse de ce que tu recherches pour l'heure. C'est vraiment un jeu à faire, mais si tu parts avec ces critères tu ne pourras être que déçu.
Pour les autres SaGa, aucune idée de comment c'est, les autres Romancing doivent avoir le même style que le 3 à priori, en étant plus archaïque.
Et sinon je n'ai pas d'autres idées vu que tu as cité FF XII, à part les The Elders Scrolls peut-être.
Edit: Au pire t'as le Zelda sur 3DS. Mais bon, j'ai trouvé les donjons tellement facile et peut intéressant...
Et niveau gestion des persos et histoire à construction libre, c'est pas ça non plus.
