Originally Posted by The Alternative
I recommend She or Allan Quartermain first.
"Allan Quatermain" is a sequel to "King Solomon's Mines", so I'd strongly suggest starting with that one. The first few volumes of my Haggard Anthology have the books in what I'd suggest as being a reasonably sensible reading order, so you could just read them in the order I've done them. Many of the books mention things that have taken place in other books, so you get the most from them by reading them in the "right" order.