We did start him in a play-based preschool this year, and he LOVES it. He wants to go all day, every day.
Definitely happy we found this school. The teacher and director seem to be happy to adjust materials in the room for my son, since they hadn't had any puzzles more than 12 pieces. It was rather satisfying (in a non-mean way) when my son spelled his name out for the teacher, unprompted, and she was pretty shocked. I think she might believe me better now that he's ahead of the curve, and that I'm not just a neurotic mom.