My son loved huge floor puzzles at that age. They ranged from 24-60 pieces and were at least 2' by 3' in size and often in the shape of an item like my example below. We had many I bought many at thrift stores and yard sales. The advantage of these is the large size of their pieces making them easier for a young kid to handle, and much easier not to loose all the pieces.
I have a favorite memory of this puzzle and my son ~2 years old. The day this arrived in the mail, I'd just unwrapped it when the phone rang. By the time I'd finished the the call my son had the entire thing put together.
http://www.amazon.com/Thomas-Friend...494&sr=1-1&keywords=floor+puzzles+thomas
