My own story up until middle school is reminiscent of most other bright young kids. I rarely did the same lessons the other kids did - I'd say I divided my time between finishing assignments and slacking off, and finishing assignments and doing my own projects or explorations.
In middle school, I really almost lost everything at the hands of a bad teacher. I don't remember how, but I got put into the normal math class - in which I would just finish everything really quickly and twiddle my thumbs. Luckily, at the insistence of my parents, I was moved up.
Anyway the real issue I wanted to bring up was where I spent my last two years of high school. My normal public high school was so-so, it wasn't bad, but neither did it afford me any special opportunities beyond traditional "honors" (read: classes with people that aren't totally retarded) classes.
Then, somewhat by chance, I found out about a different kind of school. It was a magnet school attached to a reasonably well known university in my area - but it was still public and free. Catch - you had to be accepted. Long story short, I was, and it was wonderful. The place was filled with people like myself who just wanted to learn, and each and every teacher cared about every student and would make sure he/she was working to their full potential. It was difficult, but I can't even begin to imagine where I would be if I didn't have that experience. Senior year I attended classes strictly at the university, sort of a guided transition - still under the watchful eye of the school staff, but fully immersed in a college curriculum.
It changed my whole life basically, and I'd firmly advocate having more of these places (and in fact, there are, the organization is NCSSSMST - the National Consortium for Specialized Secondary Schools of Math, Science and Technology).
If the public schools can't be fixed to not alienate their best students - then send those students to publicly funded places designed with their type in mind.