Even with a rule heavy game, it's up to the GM really to direct how heavy handed the roleplay is. Some games obviously are not the best idea but it's also why I always recommend that players don't bother with reading any rules, they should have no more than their character sheets in front of them. For this purpose it's good to go with a game with pregenerated character choices as an icebreaker for a group to see what they can do. Don't make them learn the rules or have to think on character creation, let them just play right off the bat and see what they can do with a character of their choice.
From there you can move onto some more free form play once you get a feel for a group.
I just never can recommend anyone start rpg newb group on a narrative focused game. In my experience that is what often has scared away players from trying rpgs again. Got to ease them into it and encourage and let them blossom into roleplayers.
Fiasco is the exact game that nearly lost my GF from our roleplaying group ironically. But shes gotten back in with more structured games.
Folks like to paint some of the more rules heavy rpg systems as being nothing but rolling dice but the level of narrative and roleplay involved is generally up the GM and what he can get out of a group.
It seems we are on the same page regarding this, for the most part.
The only real point of contention would be that narrativist/story/indie games aren't a good place to start for new players. I think a number of them are ideal for starting out, particularly those like
Apocalypse World and its many hacks, like
Dungeon World and
Monsterhearts. These games are played within the fiction and only when something happens that engages a rule will the GM say, "Sounds like you're trying to do <insert move here>" and then dice are rolled to determine the outcome. Maybe these aren't the best game to start out as a GM with for some, but for players they're great.
Of course other games can be played in a similar fashion if the players have not read the rules and simply have a character sheet in front of them. They have no expectations and are playing with and reacting to the situation that their characters are in or are presented with. This is a great place to start because in the minds of the players, there aren't any limitations placed on what they can do, but the situation does have a number of ways that it can be dealt with depending on the type of game being played.
Fiasco can be overwhelming because the rules are so very loose. Structure is there to stimulate creative ideas and scenes, but those scenes are left entirely to the players. If the new people are the kind to mess around in a similar fashion already and maybe do some silly improv at a moments notice, then they would have a great time. For most, having a narrower focus is more helpful to get the ball rolling and the creative juices flowing since their actions are being somewhat guided and restricted, but not hindered.
The narrowing of a focus can be taken too far and this is where I dislike those rules-heavy games. Whether the rules have been read by the players or not, it can become apparent rather quickly what the focus and intent of the game can squash the creative potential. While it can be up to the GM to make it shine, if something like D&D is being played, unless the players get into a fight conflict then they won't be engaging any of the game mechanics and are essentially playing a free-form game with less structure than Fiasco. Once they get into that combat, then the rules emerge and it quickly turns into dice-chucking and mechanics-referencing because there is little else outside of that.
Game design is there to encourage certain kinds of behaviour, so the system choice matters. Looking at two games I mentioned, Dungeon World encourages creative thinking by looking at the many options available to you and trying something interesting, because even failure is interesting and has its own reward, in combat and out of it; D&D rewards picking fights, killing things and taking their stuff to become more powerful. I'm sure it sounds like there is some bias there, I won't deny that there is, some games are better at pulling roleplaying out of people than others are.
I don't want any potential roleplayers reading this to be turned off. There is just a wealth of choice as well as a breadth of opinion. If fun is being had at the table, that is all that matters in the end. Just like any other form of entertainment, there are many flavours to suit many people. If you think of a story you would like to see played out or would like to emulate, there will be a game, or a bunch of them, out there to make that happen at the game table. There is also the
roleplaying thread for further questions and discussion; it's slow-moving but still active.