In utter shock and disbelief when I received his news, I remember I had been walking to our school's computer lab. By the time I reached it, my brain was numb and I just sort of walked aimlessly to a computer along the south wall. As I approached the desk, I told our lab teacher what I had just learned, sat down, put my head in my hands, and cried.
Looking back on it now, I'm still not entirely sure why news of his death had so profound an effect on me, but I suspect it had something to do with Carl Sagan's "real talent for being profoundly inspiring on a deeper level," as burke so eloquently pointed out.
EDIT: Just finished watching the three videos. Absolutely blown away. And no, it's not really a mystery why he had so profound an effect on so many: between the eloquence of his words and his hypnotic speech and diction, who couldn't help but we swept away by his lessons? Only he could render in such convincing detail "the view that Kepler dreamed of," (if you have a copy of Cosmos lying around, you'll recognize that particular caption's stunning photo), and so much more in the universe beyond.