One very effective way of tutoring new players can be to explain certain features on a context-sensitive basis, i.e. display instructions on how to do something based on what the player's input. ADOM sort of does this with "u"se commands instructing them to use some items the "proper" way instead, i.e. read etc.

A very, very important command for traversing dungeons both quickly and safely is the "w"alk command - in its absence, players might end up getting into the dangerous habit of holding down directional keys to travel down straight hallways, almost inevitably running into ghuls or gelatinous cubes and dying gruesome deaths. I propose that if the game detects a very high frequency in which directional movement orders (as opposed to melee combat orders - we don't really have a shortcut for clearing wererat tension rooms) are inputted, a short blurb about the "walk" command could hover on the screen, to the effect of "Try w + the direction you want to go to travel quickly and safely!" To avoid being obnoxious about players who would like to play the way they want to, thank you very much, the tutorial message would only flash maybe once or twice per game session.

If we can formulate similar contexts in which we deduce that players simply aren't aware of a helpful command, they could be handled in a similar fashion - but not learning of 'w'alk in time might cause players to become ingrained in a dangerous habit that is very, very likely to cause their untimely death - or develop carpal tunnel from all the keypresses.