Elder Scrolls III: Morrowind is worth a shout, it's notably different to Oblivion and if you don't mind the older graphics then it might suit you well. Also, isn't Zelda similar to what you're asking for? Not sure myself as I've never played it. I'm told Alundra is similar to Zelda though and I enjoyed Alundra and it's definitely what you're describing, if a little old-school in graphics (again).

The Fable series does indeed sound like it could be what you're after. You could also try the Gothic series and (I think, not 100% sure as I've not played it myself) the Witcher series.