"The game wasn't challenging, it was just punishing. Stupidly, horribly, punishing."
..try again, Shamus. At the time the game was an evolution of the narrative-less never-ending arcade action, and it renewed that without disappearing off the scale completely. I.e., instead forcing you to use cheat-codes to ever get to the end of the game, it had endless lives. That in itself made it "easy".
So to pressure you ahead, you had the 60 minutes before the hourglass ran out. Which really is more than good enough time. But it's likely that people will have to try the game a few times before they are capable of completing it. Compared to other games at the time, though - it was an easy game, and it was designed that way to ensure that people managed to play all the way through it.
Sands of Time was very similar - it drove you ahead in the story, and had difficult battles sometimes in between that would actually challenge anyone. Until they would become good enough at mastering the game that it looked beautiful when you did beat it.
Warrior Within was another good game in that sense. Unlike God of War, which is simply punishing because it gives you no good way to actually defeat your enemies on the higher difficulty-levels, and sets "challenges" for you that are almost impossible to beat without strategic use of the super-power button (there's an escape button you can hit, that charges up once in a decade) - Warrior Within actually gave you the tools and the techniques to win the fights - convincingly, without the bullshit moves. Which of course, once again, helped pace the game through the many story-driven segments.
But both of those games were reviewed by the usual console-press at the time - the people who can not imagine games actually taking much effort to make, and that are simply made to be entertainment. These are the folks that look at Mario and think it's entertaining because it's simple - and fail to understand how much thought actually goes into making the objects interact with each other in the right way, the models skid along with impossible (but believable) physics.
And the same continues now - there's a lot of people who just latch on to something "because it just works" - and let the advertisement campaign decide for them what resonates with "fans". The result being, just as you describe here - that good games are thought to be wrong in all kinds of ways. Sands of Time now suddenly being "too easy" for "real gamers".. seriously, where does that come from? To it also being too hard for the casuals (which it definitively is not, if you compare it to Assassin's Creed or God of War.
There's another part of this that affects "difficulty" as well. In some games, the difficulty is in cheating the mechanics. God of War is a game like that. You can hit things with your blades through other monsters - and finding out when the attack-animations trigger is how you end up beating it. In the same way, the game actually has several uninterruptable attacks by monsters when they attack in series. This happens several times throughout the series - a difficult monster turns up, and their super-attack is possible to defend against once. But if there are two monsters like that, the second attack will happen before you can reset your guard - and therefore you will be hit.
There have been several attempts to solve this problem in different games. God of War gave you the escape-button with the super-power. Assassin's Creed let people stand around you and wait their turn to hit you with the sword.
Sands of Time, just like Warrior Within - just didn't put you in a situation where you could be defeated, and where that would clearly be the result of a cheap move, or a failed mechanic.
And that's something entirely different than adjusting "difficulty". This has to do with making a difficult problem solvable. Or simply making a difficult fight seem difficult - as well as rewarding to win.