I want to run a sandbox game where life is cheap and survival is difficult. I'm not bitter!

I've been running narrative-heavy campaigns. I'm finding them restrictive, though, since players have pre-conceived notions of who their character is. They get upset when they have tough choices, experience consequences, or when their character gets hurt. It's like taking someone's dog to an amusement park: make sure the dog has fun, sees the sights, but don't you dare take him on any rides or roller coasters! I see a sandbox as a way to lessen the impact of negative outcomes. If an adventure goes south, the party can quickly move on to the next one. Players will bounce back from character death fairly quickly. They will be ok with the occasional loss, because loss doesn't derail the story they had in mind for their character.

I also want to largely ignore challenge rating. I find the system very unreliable as a measure of difficulty. It's handy for comparing monsters, but that's about it. I have some players who call me out on my monster choices, telling me the CR is too high. I also find that the players who complain a lot are also not very tactical. If you stand next to the monster that hits things really hard, the monster will hit you. Really hard! (I love shambling mounds! IDK why the sharpshooter always stands next to the baddies.) More worryingly, when players question my encounter building, it tells me that they don't trust me. That's fair to a large extent, since I met them online to play the campaign. All the same, it's discouraging. I like monsters with cool abilities. I want to go beyond AC, HP and damage. But players get butt-hurt when things go wrong. They also keep reminding me about the encounters that went wrong. I know it's not cool to call players sore losers. But if they can't handle a defeat, what can I do?

Travel between locations is dangerous, and can be an adventure in itself! There are monsters and villains waiting for the players. There are minor dungeons they can stumble on. If they get lucky, they'll find loot! The settlements are also not unified, so frontier law rules the land. It's very Fallout or Wasteland, except I'm not telling them the right way to deal with the problems. I hate telling players how to solve their problems. You're the player, you solve it!

And tactical combat! This follows on from the CR stuff, I guess. Winning goes beyond having the right numbers on your character sheet. The bad guys also want to win. Not every combat is winnable. Because of how unforgiving the combat would be, there will be other ways to deal with the encounters. The monsters want something: food or loot, usually. If someone dies fighting the wolves, the wolves will happily stop the fight to feast on the corpse! The bandits want to take hostages and ransom them back to the party! If you have to run away, you don't just nope out of it, you go through a skill challenge!

What about story? I wouldn't create a story arc that incorporates backstory, since I'm finding that very difficult RN. Also, I find the narrative-focused players are less interested in the problem-solving part of the game. It will be up to the players to give their character goals that fit the world. The character bonds and ideals from the PHB have some workable examples. Building strongholds could also feature in the game.

I want to run a somewhat old-school campaign, heavily based on Matt Colville's sandboxing principles.

Ironically, I feel like I'm between two disparate play styles that my players emulate. On one side, there are the narrative-focused players who want their character to be Harry Potter. Good story, but not what I consider a "game." On the other side, there are the min-maxers, who crunch the numbers on their character sheet against the guidelines in the DMG. Neither of these is very situational, and both complain that the tactical game I enjoy is "too hard." Both types of player show up at the table with a character that they believe should be untouchable. My idea of role play is using your sometimes quite-limited skills to solve whichever problem is in front of you. The narrative and min-max players have a lot of preconceptions, and that's frustrating me right now.

Rant over. xx

I personally dislike pregenerated characters, but that might help fix your problems. Kill off your party as subtly, slowly, and gently as possible, then give them pregenerated replacements.

I would have a session zero to establish what kind of game everyone wants to play. While I would not kick players out because the game I want to run is different from what they want to play, I would remind them that it is totally okay to leave the group to find a more suitable group, and leaving before the campaign starts is better than leaving mid campaign in my opinion.

If some people want to play basketball and some people want to play baseball, I would not try to force those two groups of people to play together.

I'm not sure what you mean by 'narrative-focused' characters, but it sounds like your actual issue is with player investment - your players care about their characters and take threats and challenges to those characters seriously. This is not inherently bad thing except to the extent that it clashes with the style of game you want.

I also tend to get invested in my characters. I can see the appeal of an old-school "meat-grinder" kind of game, but I would only want to play that way if I had another game going on where I could care about my character. I just don't get the rush of triumph I'm looking for by clearing out Random dungeon B6 with Fighter #8. Why should I care what that guy accomplishes? I barely know him and he'll probably die next week.

The good news is I think there are plenty of people out there that are into the style you want. The bad news is you may need to go find them. Or hey, maybe your players just haven't tried it yet, and when they do they'll like it. It wouldn't hurt to float a trial game for a few sessions preceded by an honest and straight-forward session 0.

It seems like you and your players might be incompatible. It happens. Maybe let someone else DM? 

You can talk with them but if you really want to have a "life is cheap" campaign and they want their characters to be untouchable prima donnas, then it is just not going to be possible to please both you, and them. And as a DM, you can only subordinate your tastes to the tastes of the group for so long before it wears on you.

I know you were ranting, so you probably dont want advice but as someone who has played a sandbox meatgrinder game as the DM it is very difficult to keep characters engaged and tedious to have to make up an entirely new game every time you play (mine was weekly so maybe that was a part of the problem) Eventually you run out of things to throw at them and they don't have a reason to go out into the world. There also is the problem of high level characters. Once you get around level 10 your players will become powerful enough that the bog-standard packs of wolves wont be enough for them and if they are running into the most power creatures to keep pace with them they are going to run out of rare things to deal with within the environment they find themselves in. 

TLDR: Running that sort of game losses its appeal really fast both for DM and player and takes away from player agency. 

Unless I misinterpreted what you mean by your general statement.

Just so you know, even if your current players may not enjoy a campaign like that, I would absolutely love it! It’s been too long since I played a simulationist game. And I’m also the biggest role player in my group (and almost every group I’ve ever played in), so don’t let other people get you down or tell you that, since you enjoy a gritty, realistic game, you’re not invested in characters. What’s more, I share your frustration with “special snowflake” narrativists and with min-maxers even more so. Good news is, I’ve had friends who are both, and we’ve been able to find a compromise between playstyles, so I hope you can help your friends get to the same place.

Anyway, don’t lose hope. There are more of us out there!