Andersonville by MacKinlay Kantor, a novel based on the history of Camp Sumter, the Confederate POW stockade in Georgia. This novel won a Pulitzer Prize (like The Killer Angels), and while the story is horrible, the writing is wonderful.
They’re only novelettes and they don’t use any well-known figures, but I would recommend Robert W. Chambers’ “The Street of the First Shell,” found in the collection The King in Yellow, and Poul Anderson’s “The Peat Bog,” found in the collection Homeward and Beyond.
Chambers’ novellette involves American art students in Paris on the brink of the German invasion during the Franco-Prussian War. Anderson’s novellette focuses on two Romans who visit the area around Denmark or northern Germany in the first or second century A.D.
And even though it’s science fiction, I also commend Anderson’s novel The Corridors of Time. It offers an excellent portrait of the Beaker culture circa 1800 BC.
I’ll see your War and Peace and raise you one Les Miserables. 
Oops! I forgot to mention other books!
While not necessarily historical, I just finished the highly autobiographical novel of William Somerset Maugham, Of Human Bondage. Definitely worthwhile reading.
More of a historical novel, and also great, is Darkness at Noon by Arthur Koestler.
Autobiographical and historical: Night by Elie Wiesel.
Somewhat historical and based on a true story: The Count of Monte Cristo by Dumas.
Based on a true story but not really historical: An American Tragedy by Theodore Dreiser.
Recent history put through a conspiracy theory blender: American Tabloid by James Ellroy.
You have your assignments. Next stop, the library!
I will second Night by Elie Weisel. One of the finest and most provoking books I have ever read. A very fast paced read.
If you are interested in Holocaust stuff: **Donbas ** by Jacques Sandelescu (sp?) A young teen taken by Nazi’s from his home in Eastern Europe and transported to Siberia to work as a slave in the coal mines. A tale of survival, courage, escape and hope.
Once you have a firm grasp of American History, for a much lighter side of it all ** Dave Barry Slept Here: A sort of history of the United States ** The more I read it the funnier it gets.
While The Killer Angels is a good read, way too many people take it as real history instead of a narrative novel using real people as characters. Let me suggest Sergeant Lamb’s America by, I think, Robert Graves, or that old war horse Stephen Crane’s Red Badge of Courage, or All quiet on the Western Front for something with a little meat on its bones. Somebody has to throw out the Hornblower Stories for consideration. They may all have too much testosterone in their blood for the taste of some. Those people can go read Little Women.
I would also recommend Julian by Gore Vidal. I would also recommend Creation by Gore Vidal as well.
I agree with Diogenes the Cynic that Gary Jennings’s novels have a disturbing amount of underage sexual activity but perhaps that was more normal in the times that those novels are set.
Crap, I posted this and then I remembered Justinian by H.N. Turtletaub.
Ken Follet has written at least two historical novels from what I recall, ** A Dangerous Fortune**, and The Pillars of the Earth. They are not bad but IMHO they are not nearly as engrossing as the Gore Vidal historical novels.
I’d like to second AMERICAN TABLOID, there is also a sequel to that, dealing with the assinations of MLK and RFK called THE COLD SIX THOUSAND.
Also: GATES OF FIRE by Steven Pressfield (about the Spartans and the battle of Thermopolae)
IF I NEVER GET BACK by Darryl Brock (a time travel baseball novel with a lot of real historical characters)
CARTER BEATS THE DEVIL by Glen David Gold (about an early 20th century magician, VERY entertaining, much better than it sounds)
CS Forester’s Hornblower series. No one’s mentioned Caleb Carr’s The Alienist. I haven’t read it yet and I’d love to hear some comments.
I liked Mila 18 by Leon Uris.
I can’t believe no one mentioned THE best historical novel of all times. “Hadrian’s Memoirs” by Margarite Yourcenar. I can’t recommend it enough, it is one of my favourites books.
For medieval historical fiction, try Sharon Kay Penman ( I especially like The Reckoning) and Cecelia Holland (who has also written some fine books set in gold rush California, and a science fiction book that is great, although I can’t remember its name). Holland is very psychological–try Rakossy or The Death of Attila. Both author are historically accurate, with minor changes (moving the date of a battle), Penman has historical figures as her main characters, Holland usually has a completely fictional character somehow involved in the events of a historical figure (with the historical figure only a minor part of her story).
For an excellent mystery series set during the Roman Empire, look for Lindsey Davis’s books.
Really liked Caleb Carr’s The Alienist and the follow-up novel (I think it’s called The Angel of Darkness but I’m not sure.) They’re historical mysteries, and they’re extremely detailed about turn-of-the-century criminology, forensics, and psychology. I’m not sure how accurate the history is, but they’re engrossing.
The Regeneration trilogy by Pat Barker, based on the First World War, the final book in the trilogy one the booker prize a few years back.
Mary Renault’s books move me. The King Must Die and Bull from the Sea are about Theseus; The Last of the Wine includes Socrates; and The Persian Boy is about Alexander the Great.
What I particularly like is that she tells you the cultural details you need to know without it at all seeming like she is showing off her research, and that her characters never have a false political correctness or anachronistic feelings.
Another vote for The Killer Angels, which is accurate as far as my research has shown, although of course it is fiction in inventing what the characters say. And charming they are, too.
I also love The Three Musketeers – if it doesn’t make you laugh from the start, get a better translation. I like thinking about the queen being the mother of Louis XIV, too.
Finally, I liked The Alienist very much–what I would call a possible, if not a probable, story, and I thought he pulled off the conceit of the main idea nicely. However, the sequal was very silly, all over the place and not accurate at all, I thought.
Count me as another vote for both Graves’ Claudius books and Mary Renaults’ Greek books.
I’m surprised nobody has mentioned Umberto Eco’s The Name of the Rose. I’m counting the days until his new book hits my library.
While I enjoyed The Killer Angels (as well as some of the other books mentioned), the best historical fiction novel I’ve read is Unto This Hour (Wicker). It is another Civil War novel set during the Second Battle of Manassas.
There is a Historical novel Society and they have excellent (newer) references.
http://www.historicalnovelsociety.org/main.htm
& another good site
http://uts.cc.utexas.edu/~soon/histfiction/
Tho you can’t go wrong with the “classics” suggested here.
1 nitpick: the Lion of Ireland is by “Morgan” Llwelleyn and almost any novel by her is excellent. I second or third Killer Angels, Burr the Jennings & Graves stuff.
I’d add the Michener’s Chesapeake and Texas as good ones too.