You’ve stumbled upon something that I personally think is a critical step in the process of designing a game. It is easy to overlook how a game’s tutorial can affect the player’s opinion of the game. While your intent as the developer may be to create a comfortable environment in which the player can learn the basics of gameplay before they begin, the player may just want to be thrown into the action. Remember, the tutorial is as much for teaching the basics of gameplay as it is for creating the player’s first impression of your game. Also, when crafting the tutorial, remember that whatever you decide to do can affect the experience of both new and returning players, however, without knowing the details of your project I can’t say exactly how. That said, the examples I’ve provided below should help you determine the best format on your own. Since you're specifically asking about story-based games, I've provided examples specifically relevant to that genre.
Method 1: The Guide
Having an NPC character walk the player through the controls is the method often used in Nintendo games such as The Legend of Zelda: Phantom Hourglass and Super Paper Mario (as mentioned in the question).
While this method often feels natural to the developer, it has the effect of breaking immersion. It creates a separation between the player and the character such that the two are not considered to be the same entity story-wise. This doesn’t work for most story-heavy games because they want to create a more immersive environment.
Method 2: Instructional Popups
Instead of making an in-game character give instructions on how to play, you could have a pop-up text that tells the player how to perform the contextually relevant action. This is how games like Grand Theft Auto V present control instructions. This method is generally more flexible in that you can work them into the dialogue more easily, especially if you have spoken dialogue since you’ll want the controls to be presented visually as text.
For example, you could create a situation where a character says “Follow me,” and the player is expected to follow them down a path. You could have a pop-up appear saying something like “Use WASD to move.” At some point, the NPC climbs a fence. When they get to the other side, they look at you and say “Come on, let’s go,” and continue walking. Then a pop-up appears saying “Approach an object and press Spacebar to climb it.”
I generally prefer this method as both a developer and a player because it keeps the player interested and (usually) helps with information retention. It also makes sure the player understands what they’re doing by making it impossible to progress if they don’t.
Things to Avoid
Avoid having a “tutorial” option in the main menu that either brings the player into a separate game world to learn the controls or gives a non-interactive presentation of the controls. That usually only happens in phone/arcade games, and pretty much only works if your game is very simplistic.
Also, stay away from verbose descriptions of features as they tend to put players to sleep and don’t usually allow the player much time to absorb the information. These can usually be substituted for multiple smaller steps which makes it easier to understand and remember the material.
As an amateur game developer, I’ve had to make similar decisions before. Here are some articles I’ve used in the past when crafting my own tutorials.