If you refer to the favourite toddler media thread I linked in your first post, I included some wood puzzles from Beleduc (one a world map, the other a multi-layer anatomy puzzle) in the linked thread with 15-20 pieces that my son loved around your LO's age. They were more manually workable than interlocking puzzles, while being more mentally challenging.
A word to the wise: puzzles have, by and large, been a waste of money in our house. One use and they're done forever. I buy all puzzles used. Generic puzzle games like Katamino and Blokus have had much more mileage, as has a Quadrilla wooden marble run. Wooden train sets, such as Brio, also create a puzzle-like opportunity to reason spatially while arranging track layouts, and I've found they have been longer lived.
One thing I did was to make our own inexpensive puzzles using eye-catching magazine images or pictures I drew pasted onto cardboard. I'd then just cut the pieces in a way that they fit together without interlocking. This way, you can fully customize the image, number of pieces, and degree of difficulty in dexterity at little effort or financial cost.
