A few suggestions:
Dr. Oliver Sacks -- neurologist, author of "The Man Who Mistook His Wife for a Hat" and "Awakenings," and recently "Uncle Tungsten," in which he talks about growing up during WWII and finding the growing realm of chemistry and the periodic table to be an alluring alternative to the harsh realities of life during wartime. In my correspondence with him (he lives in NYC now -- we get some of 'em, too!

), he's been charming and generous. Maybe we can get him to the A!M!
I concur about Bill Nye. I think he'd rock. Of course, I don't know the man personally.
George Carlin probably wouldn't be interested -- he's very outspoken about how pessimistic he is about humanity's potential. I don't think he would consider the "fight" to be worth the effort.
Dommage...
Yeah, Julia Sweeney, that would rock. I asked Shermer about the Skeptic Society's Julia Sweeney video, and he said it's great. I bet she could deliver a great presentation!
Hofstadter rocks... but is he a good presenter?
I think it's important to make sure that the presenters are entertainers as well as educators. Why did everyone like Phil Plait's performance so much? Was it because of the astronomy? No, it was bad astronomy!

People liked Phil's performance because of the yuks! Damnit, a sense of humor is what separates the skeptics from the believers!
How about
Ann Druyan?
More as it occurs to me...
John