My neighborhood Bitcoin shop (Decentral) offers $50 credit-card-sized plastic gift cards with scratch away private keys for those who are intimidated by paper wallets or want to make things seem more familiar to noob recipients.

I prefer paper wallets along with a list of links so the recipient can learn about Bitcoin. Also scanning QR codes is so much easier than typing in alphanumeric keys from a scratch card.