I am curious as to what story heavy games exist in genres other than the ones that typically focus on story. In particular, I am wandering what story heavy games that exist that are not in any of the following genres:
* Visual Novel
* Adventure
* RPG (personally I think the RPG genre is poorly suited for story, but it seems developers like making story heavy RPGs for some reason)

(This topic was inspired by the announcement of "The Dwarves" describing it as a "story heavy RPG".)

Two that comes to mind: Wing Commander IV and Sunless Sea. WC4 has an interesting story with some great characters and splendid acting, at least for a video game. And sunless sea is filled to the brim with great stories. Mostly short stories for each of the islands, but there are overarching ones. And the writing is the best I've ever seen in a game.

I also liked how the stories played out in Starcraft+Broodwar and in Warcraft 3, but it's not of the same caliber, and perhaps not really "story heavy".

RTS: Starcraft + Brood War are somewhat heavy in th the story, I guess. Probably SC2 too, but I have played only the trial version of it.

Half Life is story heavy, especially starting from HL2 onwards.

Some naval games. And any military themed game. (Battlefield1 doesn't count.)

Hard to say because the terms 'rpg' and 'advanture' are very broad and encompasses basically anything with a story.

Thief 1-2. No One Lives Forever 1-2. TRON 2.0. Aliens vs Predator 2.
Pretty story-heavy, IMO.

King of Dragon Pass could be defined as a management/diplomacy sim, but it's very, VERY story-centric, with a selling pitch that can be resumed as "write the history of your barbarian clan's rise to power".

Could you elaborate on that point, why RPGs are not suited for stories in your opinion?

Here it is. (Note: This applies specifically to computer RPGs.)

The way I see it, there are a couple major aspects that separate RPGs from other genres. One is the unique turn-based style of combat, in which you give your characters orders rather than controlling them directly. The other, more important (for purposes of this discussion), is that the game has mechanics that allow for character growth and stat increases.

The character growth is, to some degree, player driven; if a player wants stronger characters, she can fight enemies and accumulate experience (or whatever other way character growth works). In many RPGs, there are multiple choices in terms of how your character grows. (For example, in Final Fantasy 5, your choice of job affects which abilities you learn from battling; games with skill point systems (which I dislike for reasons beyond the scope of this post) give you choices of where to spend your skill points.)

The end result is that, in a typical RPG, the abilities of the player's party might be quite different from playthrough to playthrough.

The problem with adding a story to an RPG is that such a story can't take this into account. The story, once written, always plays out the same way. (If it doesn't, there are usually only a small number of branches, none of which really matters in the long run.) Furthermore, the story tends to be detached from the gameplay; for example, if one of the party members learns a revive spell and another gets killed in a plot event, the revive spell generally does not get used to revive the character, which feels inconsistent. (There's also the fact that, when this happens, it feels like all your work building that character has gone to waste.)

Also, stories increase the length of the game without adding meaningful gameplay, and without interacting with the mechanics that are characteristic of the RPG genre.

Maybe I'll think of more later, but that's what I have to say for now.

Terra Nova - Strike Force Centauri

Great game, btw

In good RPGs the player interacts with the "story" just as they interact with the combat part -- by picking options (move here, say this, steal that) and resolving the result through the characters' stats, skills, and inventory content. E.g. suppose there's a building with a guard parked outside -- you can
sweet-talk the guard (cha, dominate),
bribe the guard (money or item in inventory),
kill the guard (duh),
do a quest to get invited (procedure call),
sneak in through a third-story window (invisibility/stealth, climbing/flight)
find a secret way in through the sewers (thief class, int, procedure call).

How isn't it gameplay?

Honestly, terrible RPGs have more in common with story-free RPGs than with good RPGs with stories. Terrible RPG = story-free RPG + terrible cutscenes.

Now, plots where a character gets killed in a cutscene despite resurrection being available, or the goals of the party do a 180 without any input from the player are bad. I have no excuse for them, because they are just bad.

As for not much choice in CRPGs -- that's true for tabletop too. Both good CRPGs and TTRPGs are ruled by social contract. "In this game, you play Lady Tehpwnzor McAwesome and her faithful comrades who set out to defeat Emperor Grimdark" isn't much different from "I'm thinking of running Red Hand fof Doom, do you want in?" And even if the group is allowed "total" freedom of choice, there are still underlying assumptions that (1) they're going to interact with the material the MC presents in some way, and (2) individual players will go along with the majority's choice and find a reason for their characters to do so. It's not fair to compare a specific CRPG to, say, D&D. D&D is not a game, the specific thing you're doing with your gaming group is.

I actually consider this to not be story (though the quest could possibly have a story, of course). In fact, I can think of an example in an early RPG that I consider to be story-free: Ultima 3.

In Ultima 3, one of the ways to get money is to loot the town of Death Gulch (this can be done repeatedly until you have enough money). However, there is a guard blocking the door, as well as other guards in the town. Hence, you have a choice here:
* Bribe the guard (but that costs money)
* Kill the guard (but now all the guards are hostile and after you; I hope you are able to handle them, or that you are able to stop time (which costs either money or more than half your maxed-out Wizard's MP)
* Don't bother, and instead get your money from one of the dungeons (my preferred solution, actually).

There are other guards, but at least one can be avoided with an alternate route.

Even then, certain chests (those right next to the shopkeeper) will turn the town hostile, so you can either avoid taking them (and get less money) or take them anyway (and be prepared to fight/stop time to escape).

In conclusion, your example is gameplay, but it doesn't qualify as story to me.

(By the way, have you played Ultima 3?)

Any genre can have story heavy games, at what point would you define a game story heavy?

I would say BioShock Infinite (FPS) and Her Story (Interactive movie)

You do know there are RPGs that aren't turn based right? And of course the story can take player progression into account. You need to make a Thief character to access the Thieves' Guild storyline, you need to make a Mage character to access the Mages' Guild storyline, etc,