I'd also like to comment on something else you said in your original post, which I very much agree with.
Every game with RPG elements has a perverse tendency to adjust difficulty downwards for more skilled players. The skilled player is more likely to find all of the heart pieces, or to find that hidden Sword+5, or to be willing to grind a bit in order to level up.
However, I don't see a way around it. What sort of reward can a game offer players except for rewards that are useful in-game? Even games like Oblivion, which scale enemies as you level, can't avoid this entirely. First, we note that many players don't like this aspect of Oblivion, and it clearly removes a lot of your incentive to level up. Second, the skilled player then just relies on maximizing his capabilities at a given level, so there's a lot of focus on working on skills that don't level you up.
More skilled players are going to be better able to get the game's rewards, and those rewards will make the game easier.
