Well, I don't want to implement Navi The Fairy, and having a companion when you're supposed to be out Lone Adventuring is kind of beside the point.
When it comes to introducing game mechanics gradually through gameplay, that's something that in my non-professional games I've created (notably Alden Ridge, but also a few others I've done) I've always focused a lot on. Those were also all non-procedural, though. The problem is choice: Portal is linear and there are only a couple of solutions to any given problem (if even more than one). Consequently, they could focus all their talents into that space, and make the game amazing -- for mostly one playthrough.
The challenge with a sandbox game is that players want to get to the parts that grant them freedom as soon as they can. That's part of why there are some branching elements of the intro mission -- to give the sense of choice right from the start, even when there really isn't terribly much meaningful choice in that tutorial itself. But as soon as players are done with the tutorial, they're going to want to be able to jump into the game itself right away, and actually get to playing -- but have any new elements that are introduced (such as EP and missions, most notably) either be something they can figure out on their own or that they are told about at the time.
The problem is when you get into "Megaman, Megaman!" territory, as this video so eloquently (and profanely) puts it:
http://www.youtube.com/watch?v=8FpigqfcvlMThat's been my main gripe with Skyward Sword, for instance -- they could have cut about half the dialogue, and the entire character of whatever-the-master-sword-robot-woman's-name-is, and it would have been a stronger game. As it was, they constantly had her coming in to tell you stuff they'd just told you, but in slightly different words (or not even that). And the amount of hand-holding seems higher than I recall from OoT, but I could be wrong.
I guess my challenge is that I have to do a certain amount of "Megaman, Megaman!" because in a procedural sense (or most sort of strategy/simulation game in general) there's just no way around it. And, hell, that "Megaman, Megaman!" design pattern is epidemic in modern games, and doesn't seem to bother most people that much (though it sure as heck bothers me). So doing that just a little bit, and doing it sparingly, is probably all that's needed.
I actually feel like zebramatt pretty much nailed it with his suggestion; there may be a few other things to layer on after that, or some alternate things that could be tried if someone has a better idea for some parts of it, but overall that's really just what's unavoidable, I think.