A writer named Tim Rogers posted an opinion piece on Kotaku recently on how games handle tutorials, and what they could do to make it a lot more convenient for both veterans and newcomers. I think he has some really good points. Be warned: it is a giant, giant wall of text, and will take you a while to read the entire thing. But if you're cool with that, you may find it interesting as I did.
http://kotaku.com/5354035/stop-telling-me-what-to-do

I remember hearing Annie Hall of Obsidian fame mention at the Codex that publishers practically REQUIRE tutorials.
So it may be the publisher's fault for assuming that their customers are mentally deficient.

From what I can recall, the Fallout 2 temple of trials was put in at the publishers request, as a tutorial stage.
The worst part is, the early Arroyo quests are very tutorial-like, so for veterans it can feel like a double tutorial (of course you can skip the arroyo stuff, but if you play a character with low combat stats it is helpful to get that easy XP).
Will have to read that article later, need to sleep! (midnight here atm...)

tl;dr
I think a nice compromise is to make tutorial a separate 'game' from the main game (i.e. Baldur's Gate 2*, Final Fantasy Tactics), or to make tutorial sections within the main game skippable ('press Start to skip the tutorial'), or at least optional for the second playthrough.
*=There's still Irenicus Dungeon, though...

I liked the way this guy suggested what a tutorial would be like for a zombie shooter. A character introduced early sends you on your way into the castle. You encounter your first zombie. Someone already acquainted with games like this just blasts the guy away and continues forward, but for the unaware, the zombie shambles closer until a message pops up explaining how to aim and shoot. If the player is shooting the body but not the head (a must for zombie death), the head is gradually displayed in a more obvious fashion, until finally the side character runs into the room and screams, "AIM FOR THE HEAD, YOU DOLT!"
This is the most effective way for a tutorial I have ever heard. Good on him for thinking of such a great example!

Can't say I read the article. I tried, but when half the thing seems to be about Japanese culture (can't blame them for catering to the target demographic of the site, but still...) I feel alienated, so maybe I missed this.
That works for incredibly simple things. Let's apply that logic to crafting, sniping, or anything more complex than "click the left mouse button to shoot".
Also, what about people who aren't used to shooters? They might not even know how to shoot, or they might miss the thing entirely.
Or, let's say you are the guy who actually needs help. You whine that you wasted all your ammo and wish some tutorial had helped you sooner.
Or, you are just someone who isn't good at aiming (there are lots of those people). You bitch because you get the "evil tutorial" even though you know how to play.
Honestly, from what little I have gleamed this article seems like just another whining article. Imagine if someone who hates flight sims tried to explain how to make DCS: Blackshark a better game. He might argue that it should be more streamlined and have much more arcadey physics. And he is probably right, most people would enjoy the game more if it were like that. But that isn't what the game is about. The game is about heavy-duty sim players.
Same thing here. The tutorials aren't meant for people who know how to play. They are meant for those who don't, or those who want to learn the controls without reading the manual (like me :p). Honestly, I rely upon tutorials these days, if only to figure out which control scheme a game uses. The melee key in FEAR (2), Call of Duty (4), and Republic Commando are not the same button. I can either randomly press buttons, or wait for the helpful pop-up.
Honestly, the best method I have seen has been the kind where you have that little checkbox that says "Stop showing tutorial pop-ups". But some people just get so offended the moment they think a game is babying them, so whatever :p

Wow, a Kotaku article that doesn't suck.
Interesting read, but I usually come from the camp that's all "just tell me what to do in a small little corner in a separate tutorial mission that I don't need to do".

A simple tutorial level slider would probably satisfy most of the camps involved. Set to medium by default so you get the popup tip the first time you take an action but put it up high and it reminds you a few times as you play the early levels, set it to low and it basically shows you what buttons do what and let you go

it's as easy as this: "Tutorial? Yes/No"

I started to read the article but he somehow alienated me with his roundabout way to say thing. So here's my take on tutorials: I usualy dislike them but only when they are part of the main game and unskippable, but have often no problems with them if they are a separate level you can chose to do.
Deux Ex is a good exemple that comes to mind, as it contains a bit of story, and is the only time when characters will refer to your mouse and keyboard. Sacrifce also had a well-done serie of three tutorial maps that served as an introduction to the unusual mechanics and also the alien world. It also helped that Zyzzyx was voiced by a very good actor. Thief has a tutorial level that is part of the main game but gives you the option to skip it, and so do System Shock 2. I also very much enjoyed the Bloodlines tutorial, if only because John di Maggio is an excellent actor and the whole thing has some little differences depending on your clan, plus you still got the option to skip it.
Another interesting way of doing it is in Thief 2: on normal, you get tutorial popups during the first mission, that you can ignore if you want, but they will be absent if you play in a higher difficulty level. Halo also does something like that by skipping the small tutorial if you play at something higher than normal.
Bottom line: give people the option to skip it if they want, and don't make it too obnoxious.
PS: forgot about Beyond Good & Evil. That one doesn't really have a tutorial but it keeps reminding you of the keys you could use when in a certain situation. It is very subtle, unobstrusive, and can give a hint if you get stuck in some place. Actually it does have a very short tutorial at the start but it is really well tied to the story that I never thought of it that way. Sands of Time is a bit the same in that respect. Guess it's also about the way you present it.

Very true, I do quite like VtMB and Deus Ex's tutorials because A) You can skip them and B) They actually flesh out the characters' personality, as opposed to something like KOTOR, where it's unskippable, is delivered by a throwaway character in a droning voice, and is insultingly basic.
Oh, and another game with a great, optional tutorial is Tomb Raider Anniversary. The Croft Mansion is actually a backstory enhancing diversion in it's own right.

More like: Tutorial? Y/N
Yes and No are way too friendly.

At the highest level, the game should be set to mommy mode.

+1

Going even further, the Y/N prompt should show up on a console, and the only way to answer it is through a keyboard.