You could give Legends of Anglerre a try, it's based in the FATE system. Very few rules, a lot of customization for characters and a lot of power for the GM and the players at the same time to craft a great story.
An advantage of this option is that once you get used to how the rules work there are a lot of other FATE-based games that work the same way, and which cover different genres to fantasy. Starblazer Adventures, Strands of Fate, Dresden Files. One thing worth noting is that it also has rules for vehicles, organisations, and nations all in one book, as well as advice on setting creation. The actual rules are quite slim.
Another potentially low-combat, simple rules system is HeroQuest. Characters are highly customisable, although there is no "minigame" of building characters - it's not as if the customisation makes your character stronger or weaker in the game.
HeroQuest does need a GM whose good at kicking things off with compelling situations, and whose good at adjudicating the outcomes of PC actions on the fly. A GM who ran good skill challenges in 4e would probably be a good HeroQuest GM,
Heroquest (I recommend version 2 strongly) is a system which takes some getting used to, for both GMs and players. If you take to it, the sky is the limit, but a lot of people don't or won't. It's not a system where the detail of how something is done usually matters, just what the results are. I've seen a two-weeek seige resolved in two dice rolls, and if that isn't to your taste it probably isn't for you.