Difficulty isn't a bad notion, nor do I think that it was difficulty that soured some people on Sekiro. I gave up at Genichiro in the tower - it was just too infuriating in the end and I honestly couldn't see what I was getting out of it.
Funny thing is, I'm pretty sure I've had harder encounters in other FromSoft games and overcome them - Lady Maria, Ludwig and O&S all spring to mind - but somehow the design of Sekiro makes the hard-won victories feel less rewarding and the drive to overcome something, less compelling. I can't explain it. The boss rush feel, the singular approach to combat, the lack of meaningful discoveries or upgrades and the miserly attitude to consumables made me feel more like a battered and broken survivor than a victorious champion (compounded further by the Dragon Rot mechanics).
I think that's why it felt more difficult, not because it was, but because of the way it made me feel about each victory and failure.
It was the opposite feeling for me, and I hate to be that guy and come out of my basement and say you are playing it wrong. But it seems like if you truly struggled and somehow barely got past a boss with a sliver of life left, the victory is indeed hollow. But in Sekiro boss fights are all or nothing. Either you completely downloaded the boss to the point where the fight ends in seconds or you die instantly. I know this requires patience to study the boss, but this game is NOT meant to be played like a souls game. Its basically Parappa the Rapper with exploration.
Sekiro stands apart from other souls game in that from the get go you are fully capable of taking down the strongest of foes according to story and lore, while in souls games you start off as a puny being, so hollow victory should not be felt by the player in sekiro, unless the game hasn't clicked for them of course. Every battle of Sekiro should be fought like a battering ram, and not with timed dodges ala souls, and after defeating a boss you should feel invincible. There is no soul farming to upgrade your attack damage, no technique or hidden mechanic, or popping up your shield and playing mexican standoff with boss. Its just your sword that can either hit or block. Its basically a rhythm game.
Since you stopped at Genichiro, which I considered to be early game, I understand why this idea hasn't popped up.
I was struggling myself on my first playthrough, even I couldn't get pass madam butterfly for days. Then my friend told me to stop playing it like a souls game and voila, every boss fell like butter even the infamous final boss.