I also recommend the Melissa and Doug puzzles. They make many different sizes of wooden puzzles. Cardboard warps and gets icky too easily. The wooden pieces are tactily pleasing and last for handing down to younger sibs or friends. My youngest was a puzzle nut from about 1.5 to 2 years old. She stopped after she got to doing 48 pieces independently, and switched to working more seriously on reading.
You can also look for the wooden stacking shape/color sorters or the type that require the child to reproduce a pattern with stacking rings or beads. If your little one reads or knows letters and sounds, the alphabet matching puzzles that have a top and a bottom half with a picture on the top and a letter on the bottom are fun.
