Recommended reading: http://www.gamespot.com/users/masterpinky2000/show_blog_entry.php?topic_id=m-100-25778941&om_act=convert&om_clk=soapbox&tag=soapbox;subject;1 as it is the article which prompted this reflection.
Oh, doubtless games can have both a great narrative and be particularly hard, but the harder the game is, the more likely it is you will spend more time with certain sequences than you would like.
The key would be to fit the slower pacing in with the narrative. If you want to tell a story, interruptions are bad with a capital B, so having to reload too often ruins the game. Take Indigo Prophecy, which was one hell of a narrative driven game: playing it on higher difficulty settings would ruin your experience of it as it would likely disrupt the flow of events. Then again you can't make it too easy. Prince of Persia 2008 was a visually stunning tale but it was unbelievably forgiving and so was unengaging; there was so little challenge in playing it that it failed to capture your attention.
On the other end of the spectrum there's Demon's Souls, which I have not played, but after reading review after review of it, it seems to me it's mainly praised for its grueling difficulty and interesting multiplayer interaction. Not once have I heard or read someone praise the "engaging storytelling, which will keep you glued to your seat for hours on end".
Another perhaps similar game comes to mind: Diablo II when played on Hell difficulty. Everyone could beat Normal, Nightmare was a warm-up (fun, yes), but ultimately Hell difficulty was where you really put yourself to the test, and where the greatest rewards lay, both in terms of loot and in terms of personal accomplishment. But it didn't stop there: you could create a "hardcore" character, ie a character for whom death is permanent, to really test your skills as one mistake could rob you of months of work. Diablo also had very little storytelling, but nobody really payed attention to that as they were too busy organizing their skill trees.
More examples come to mind. After having played through Modern Warfare 2's rather short but climactic campaign I found myself very much unsatisfied. I recognized the work put in creating such a cinematic gaming experience, short though it may be, but the catharsis that was at the end of the first Modern Warfare was not back to greet me at the end of the second. How so? Well, I could argue the campaign's storytelling liberties, the psychologically shallow characters (of which I was nevertheless fond: go Soap!), etc. etc. but that wouldn't take me anywhere.
The difference, I reflected, lay in the difficulty. MF2's campaign is supposed to be an adrenaline fueled rush, and in some cases it's true, but I found that on the normal difficulty level it was all too smooth. You could rush through the game in a matter of hours, and certainly you were intended to rush through it, just not in that particular sense. I compared this with beating Modern Warfare 1 on the normal difficulty level, and intense gun fights came to mind, fights in which I always had to keep my head low and proceed carefuly. It gave the game a sort of intensity which did keep me glued to my seat as I pondered the various tactical dilemmas. The most notable consequence of this was that you often had to stop your advance, take cover, and fight out an area room by room. This only got better as you increased the difficulty; and as you increased that you also increased your personal satisfaction (Mile High Club on veteran anyone?).
Now, I haven't played through MF2 on higher difficulties yet, but the difference was nonetheless clear from the start. Seeing how it was so easy, it was difficult for me to get attached to the characters, to feel that I had gained something through effort. This difference for me is the difference between a good single player experience and a bad one. Had the Sands of Time been as easy as PoP08 I would never have completed it, had it been as hard as they say Demon's Souls is, I would have gave up on it in frustration. Just as it was, it was perfect. But in the end, did I play it because it gave me the opportunity to fight interesting monsters, or because it was a beautiful story?
Another example: Bioware games – Jade Republic, KotOR, Mass Effect, Dragon Age – are all story driven games whose focus is arguably storytelling. Anyone who has played any of these understands this. When playing them I have no wish to prove my skills, but merely want to be immersed in a story. That's why it is very frustrating to reach a point in the game where you are pitted against seemingly insurmountable odds and are forced to reload until you figure out a way to win the fight. The point of KotOR, for instance, is not to prove how clever you are by defeating waves upon waves of sith and then finally taking down Malek himself but to experience a story on a deeper level than just watching a movie and on a more interactive one than reading a book. The fact that in order to achieve victory you may need to employ every ounce of cunning you possess can only add to the sense of accomplishment, but in the end it is not necessary to fully enjoy the game.
My experience shows that both narrative and greater difficulty can be integrated into a game, but they will not work harmoniously together. One of the golden rules of storytelling is this: Never let the reader remember he is reading a book/the viewer that he is in a theatre/ (and by extension) the player that he is playing a video game. Such risks, however, are intrinsic to all videogames, not merely to the hard ones, as they all are, in the end, in some measure, tests of skill.