I'd define challenge as a ratio of time spent playing vs time spent progressing. If you fail 1 out of 3 attempts at a combat but are only set back a minute or two each time, it's not nearly as challenging as a game where failing one combat out of 30 sets you back an hour.
Better define it as the amount of (useful) skill required to progress, not "time".
Your definition is not bad, but in this form it only defines "grind". Of course all challenging games require time and skill, but there are also "grindy" games in which progress is unrelated to skill, because the game is just damn stupid.
I think human intuiton has always been that games should determine the "best" people in certain activities, and this makes challenge a statistical problem, i.e how well the player success falls into a random distribution related to their skill.
This is important because games are not only for entertainment. In general, humans seem to have a tendency to favor games that allow to precisely determine the skill of the player (not his commitment to the game).
Therefore challenge means that the game can not be progressed by random input, only by skill (this will mostly be motor or intellectual), and no one can "cheat" by compensating skill through repetition.
So, a game is worthless if everyone can beat it without skill, and so is one in which no one can make progress except by endless repetition. For example bowling is quite a challenging game, but not if the pins were 1m from the player, and also not if they were so far away that no one can hit them. In this line of thought, some games require superhuman skill like QWOP, and are therefore quite pointless. Other games require no skill at all, like Dear Esther, and it's not surprising that most people don't even consider that a game.
The conclusion is, challenge based on skill is the only relevant metric to define a game, and "immersion" is completely irrelevant. (Immersion is only relevant for the entertainment value).
Immersion is also highly subjective (regular gamers lose the ability to immerse themselves anyway), but skill can be developed, and this why only challenging games are always rewarding. And only if a game is challenging and the challenge is also rewarding (because success in the game is fun and the player can improve his skills and thereby learn something), it is also a good game.
Good games are for example Pool, Bowling, Chess, Poker ... Most computer games grossly favor short term entertainment value (graphix) over challenge and are therefore not good games.