We were also very happy with ds's Montessori preschool (he was there when he was 4-5, the year before K). It was great, and much better than public K is!
I'm also waffling on the play-based versus academic preschool. If your ds is ready and interested in academics, there's no reason to hold him back. However, you really are going to run into problems finding a program willing to *really* accommodate a 3-year-old at his academic level, because normally developing children just do not need/want the kinds of things that highly gifted children need/want.
So if you can't find a program that will really work with him, play-based may be your best bet -- at least they won't be reteaching him things he already knows. I see this in my ds5's k class. They're teaching him phonics -- he's been reading quickly and well since he was 3! The phonics program is making him rethink his instinctual spellings (which are usually right), and it's just not a good thing. At your ds's age, the way he's learning is probably the best way for him, and any attempt to "reteach" him skills he already knows will likely be a step back. *That's* mainly why I'd be wary of academic preschools.
Good luck! Your ds sounds like a riot -- love the CPR.
