Visual cues are nice, and even desired, but gentle introductions outlining how to get started are as well.
My method is to get 3 random craigslist people and pay them $50 bucks to play with the app for an hour. Record them struggling and have them talk through their thoughts and how they use your app. You will learn more from that experience than anything else.
The 'obvious' lock screen camera thing on the iPhone is a perfect example of something that I haven't seen anyone figure out on their own. It doesn't look or behave like anything else on the iPhone, including the only other interactive element in that same lock screen. Once you DO know, the cues are nice reminders.
The Pudding Monsters example is terrible too, as it precisely a UI walkthrough. Minimal, because well, the UI in that game is minimal, but it is explicitly telling you what to do and how to do it. (BTW the game is wonderful)
I think I had even read about it, but never bothered to try it until now.
Discoverability needs to be layered. Come over and watch my Dad use your app. It's astonishing how much we take for granted.
With a recent project I watched a few totally inept testers discover all the features with no problems, but after launching it became clear that most of our power users were not discovering features. A quick bit of intro text and everybody is happy.
I think there's room for both, but I think it's nuts to assume that the people who really do need a walkthrough will:
a) Remember it
b) Be able to find out where to get the tutorial again, unless there's a giant "?" button at the top.
I think your vision is skewed, if all you require is "a quick bit of intro text". I've seen tutorials that are minutes long, and it's just awful.
Most applications don't need a complex UI and shouldn't make their UI more complex or difficult to understand than it needs to be (this, I feel is the OP's real gripe). Its rare that your UI need be so complex that a UI walkthrough should actually be necessary. Most users of most applications don't want to (and won't) go through a learning process, they just want to 'do'. That said, I agree with you that sometimes it is necessary/helpful.
> They act as the equivalent of standing next to someone
> and "showing" them how something works.