We were in a similar situation. We went with a gifted private school at 4 (figuring if it didn't work we could always try public K 2 years later). When you put a gifted kid in with other gifted kids the dynamic is really interesting. They seem to really "get" one another in a way that does not happen with NT kids the same age. My kid does not appear outwardly gifted either (acting is one of his gifts I think). We did not want our guy getting into bad habits and coasting through school. So far things are working out pretty well.