Tanagram puzzles might be something.
The struggle with this age is that when the pieces don't fit easy or perfectly, it can be frustrating. My DS would cry about it. It's just part of the process. As others mentioned, those big floor puzzles are easier for little hands.
If you aren't opposed to using a tablet, there are many puzzle apps that are free and perfect for early puzzle interest. The pieces can't move so the frustration is removed. Sometimes when my son just couldn't emotionally handle the frustrations of a physical puzzle but needed to work on one, I would use apps and I feel that it was very positive.
As for looking ahead, you are likely correct in your thinking that school may not meet many of his needs. I started reading these forums and then finally asking questions about two years ago and I was in knots about it. Here we are, DS is just about to turn 4 and his preschool teachers are just as concerned as I am about his future in school. We still haven't decided where to go. It's a process.
