TL;DR: When selecting a wallet to store private keys, personal preference and risk tolerance are paramount. Paper wallets, where the seed phrase is written down, risk damage from outside elements or wear, so metal backups like stainless steel for durability are preferred. Brain wallets, relying on memory for seed phrases, are vulnerable to forgetfulness and accidents. They also tempt users to choose weak seeds. Therefore, metal-based paper wallets are advised over brain wallets. For even greater security, consider codex32: a tool that forgoes all electronics that divide the seed into recoverable "secret shares" that then reconstruct the original when combined.
When it comes to choosing a specific type of wallet to store your private keys (seed phrase), it ultimately comes down to your personal preference, how comfortable you are with the various tools, and the level of risk you are willing to take on. Both allow the offline storage of your seed without the use of computers, which is ideal for increasing the security of your bitcoin holdings, but each still has drawbacks.
Paper wallets, where the seed phrase is written on paper, may be lost and are prone to physical damage by fire, water, chemicals, and ordinary wear. Instead of paper, it is highly recommended to use a strong metal to store the seeds, such as stainless steel or titanium, with a high melting point and good chemical resistance. As such, many Bitcoiners use a metal backup tool, though acid-free paper could work in a dry and fireproof location.
Brain wallets, where the seed phrase is memorized, may be forgotten or lost due to memory lapses when an accident or illness affects your mind or can be extorted. Another issue with brain wallets is that it encourages users to choose weak seeds that are too short, too highly structured, or that exist in printed literature. Even if these seeds are tweaked, they lack the information to withstand an attacker with enough computational power.
Due to brain wallets' susceptibility to memory loss, of the two choices, we recommend a paper wallet, in which you ultimately transfer the seed phrase to a robust backup device made of robust materials. For even greater security, you can use codex32, a totally non-electronic tool that creates several "secret shares" that split and re-split the backup seed phrase. This allows the original seed to only be recovered when enough of them are brought together.