This is the one I recommend to pretty much everybody, and they all rave about it:
We Wish To Inform You That Tomorrow We Will Be Killed With Our Families: Stories From Rwanda, by Philip Gourevitch.
I found Origins Reconsidered : In Search of What Makes Us Human by Richard Leakey to be a fascinating exploration of human evolution and just what forces lead to make us what we are today. It also has some autobiographical elements to it to help make it a good read.
If you want to read about the OED I have to say I prefer Caught in the web of words by K. M. Elizabeth Murray.
One of my all-time favorites, if you’re interested in history and women and fabric and all that stuff, is Women’s work: the first 20,000 years by Elizabeth Wayland Barber. All about the development of thread, weaving, fabric, and so on. Fascinating stuff.
Or, if you need to beef up your reference section, buy Brewer’s dictionary of phrase and fable. The preface in the 2000 edition was written by Terry Pratchett!
If you haven’t read Guns, Germs, & Steel by Jared Diamond yet, I highly recommend it.
One more shout-out for Henry Petroski. The Pencil is the best piece of popular history of technology that it’s ever been my pleasure to read.
I also got great satisfaction out of a slender little book called A History of the World in Six Glasses, by Tom Standage. It’s surely the first history of world civilizations told through beverages (beer, wine, coffee, tea, cola, and water). Brisk and engaging after-dinner reading, ideally with the appropriate quaff nearby.
To all the plaudits laid across Bill Bryson’s broad shoulders, I can do little to add – except that his European travelogue Neither Here Nor There and his British one Notes from a Small Island are among my favorite books of any kind by any author. I say travelogues, which they are, but I also wouldn’t let either deter you from visiting the places he writes about. Of those I’ve been to so far, I’ve found most more enjoyable than did Bryson, who’s an idealist, a bit cranky, and easily let down by the state of the world. More importantly, though, he seldom fails to amuse as he educates, and is not infrequently pee-your-seat hilarious.
I’ll heartily second Surely you’re joking, Mr. Feynman. Even if you don’t care about physics, the story about how he cracked into the safes with the US’s nuclear secrets is priceless.
The sixth beverage in Standage’s History of the World is not water – which is dealt with often enough anyway in the book – but distilled spirits. Excuse please.
I read A Mind of Its Own: A cultural history of the penis by David Friedman this spring and lurved it. It’s pretty much about what the title says.
The Spirit Catches You and You Fall Down by Anne Fadiman is pretty good and shocking if you weren’t aware of what happened to the Hmong after the Vietnam War. I wasn’t as it definitely wasn’t covered in my American history classes.
I second The Professor and the Madman.
’Swimming Across’ by Andy Grove
Born Andres Groff in Budapest just before WWII. He grew up in the occupation, escaped the Nazi’s, made it to NYC with $20 in his pocket. Went to a shool in NYC while living with a distant relative. Got a job offer in California, went to school there (Stanford?) and later becam CEO of Intel. Hell of a story, great book.
Pretty much anything by Carl Sagan or Barbara Tuchman. Of course, they’re both dead, but what are you gonna do?
I second (or third, or something) Mary Roach’s Stiffed. Fascinating.
I was going to mention Alison Weir, but I see you know about her already.
I just read Princesses by Flora Fraser – about the daughters of George III. She isn’t as good a writer as her mother, IMO, but the story was very interesting.
Will You Miss Me when I’m Gone?: The Carter Family and Their Legacy in American Music is definately worth the read, too.
Seconding A Bright Shining Lie, The Making of the Atom Bomb and pretty much anything by Henry Petroski.
If one is into seafaring tales, may I suggest On the Bottom: the Raising of the U.S. Navy Submarine S-51, by Edward Ellsberg? This is a cracking good read, describing a herculean, 18-month effort to recover the sub after it was lost in a collision with a freighter off Long Island in the early '20s. Ellsberg was one of the officers supervising the recovery team, who struggled with primitive diving equipment, appalling conditions, and an unending series of technical problems that routinely threatened to scuttle the whole mission, right down to the last few yards of the sub’s transport back to the New York Navy Yard.
Into Thin Air The only non-fiction book I’ve read that I couldn’t put down, started and read straight through to the end.
Steven Jay Gould’s Wonderful Life I think a lot of what’s in it has been dis-credited since (it’s over 25 years old) but it’s a great read, you’d never think that analysis of biramous appendages would be so compelling.
Last Chance to See by Douglas Adams (and some other chap), searching for endangered species.
Very easy read, simple to understand, and you will go running to write your congressmen afterward.
Young Men and Fire by Norman Maclean, and Beautiful Swimmers by William Warner are two of my all-time favorite non-fictionbooks.
I bought that one a few years ago at a garage sale for .25. Best quarter I ever spent. 
I know other people loved Adams for his science fiction but I loved him mostly for that truly terrific book.