TL;DR:
Begin your Holmesian adventure with short stories from The Adventures of Sherlock Holmes and The Memoirs of Sherlock Holmes. Continue with the early novels before moving on to the later short stories. End with The Valley of Fear and then The Hound of the Baskervilles, to see Holmes (and Doyle) at his finest. The order is, for the most part, chronological.
Phase 1: Start with short stories from the first two series.
The classic Holmesian tale involves elements of deduction from seemingly nonexistent details, whether they be a piece of fabric or a burn mark. To understand the way Sherlock Holmes thinks, you need to read one of these to catch a glimpse of his methodology. Holmes is not just a man; he is a character for study, and his depth is what puts Doyle above so many other writers in detective fiction. He's inscrutable, irrepressible, and always unpredictable, and you cannot just pick up, say, The Hound of the Baskervilles and understand the complete persona of Sherlock Holmes.
The short stories are, of course, the best place to start. In 20 or so pages, you can see an example of the sleuth's mind and personality, while getting to used to observing him work, through Watson. While there's no typical story, I'd recommend starting with one from The Adventures of Sherlock Holmes. A Case of Identity would be my pick, as it begins with some marvelous deductions by Holmes and ends with a resolution nobody could have seen coming - yet at that point, you see the pieces fall into place as clear as day.
You might be tempted to start with the story published first in that collection, A Scandal in Bohemia. Don't. It is an outlier in the Holmesian saga, an unusual and compelling tale that I think is best appreciated only after you get to know the detective. It shows parts of his personality that are only rarely apparent elsewhere - love, even - and involves a case unlike any other. It is atypical, and while it might interest you, I'd recommend starting with something more ordinary.
The Adventures of Sherlock Holmes and The Memoirs of Sherlock Holmes are rather similar in style, I feel, and so the stories can be read in various orders. There is extremely little overall plot change within them, and while in a certain story Holmes may reference past cases, they are largely self-contained. Doyle's style is roughly constant, if memory serves. This collection can be picked up and put down at any point.
I would, however, advise reading The Final Problem last out of all of them - for continuity's sake - as you acknowledged in the question. It is perhaps one of the most important short stories in the initial arc. I also happen to like reading The Adventure of the Naval Treaty directly before this, because I love it, but it's not mandatory.
Phase 2: Mix something else in - A Study in Scarlet or The Sign of the Four.
After a while, you may get bored. Each short story will challenge you, but the format can get tiresome after 24 of them. I encourage you to try one of the longer standalone works. I would prefer A Study in Scarlet or The Sign of the Four, which go into Holmes' methodology in more detail and present a story arc - which you don't see as much in any of the short stories. Both of these books were published before any of the short stories, but they can be challenging to slog through. I'd wait until you're comfortable with the style before going on to these.
I suggest mixing them in after reading perhaps ten or twelve short stories - or earlier, if you want. But read them in one sitting. Do not start one and then go back to the short stories. Confusion may follow. I also happen to think that there are many cases where reading a book from start to finish is the best way to appreciate it, and this is one of those times.
Phrase 3: Go back to the new short stories.
Note: Re-read The Final Problem, to refamiliarize yourself with it and see how the arc it begins evolves into the next series.
Doyle, feeling extreme pressure by fans, brought Holmes back from the dead after killing him off - in a fashion many may know about, but which I'm not going to reveal. He eventually published The Return of Sherlock Holmes, another series of short stories. In my mind, these are worse than the original two collections (after all, there was an 11-year gap between this and the originals!). They feel forced, and the plots get ever more intricate, astonishing, sensational and, quite frankly, hard to believe. I find some unsatisfying; at any rate, I can tell the difference in style.
Try to read these 13 together, as a group (start with The Adventure of the Empty House, Holmes' return). Don't mix them in with the other two collections; there's just something wrong. Maybe others disagree. At any rate, quality aside, I do feel like The Return of Sherlock Holmes was written with suspense in mind, not the pure intellectual investigation. My same criticism holds for His Last Bow and The Case-Book of Sherlock Holmes. However, I don't remember them all as clearly as I remember the first three series.
Phrase 4: Finish up the novels.
First, read The Valley of Fear. It's likely my least favorite of the four novels - again, I think suspense plays a bigger role than pure mystery - but it's still worth a read. I'd recommend reading it last, so you keep a rough chronological order for the novels, but I think it lacks a sense of closure.
Finish off your Holmesian adventure with The Hound of the Baskervilles. Doyle wrote this to fight off the clamor of fans when Holmes was "dead", and so it was a throwback, in a sense, but it is quite self-contained. Doyle creates a unique cast of characters - none too hard to believe, in fact - and keeps suspense and intellectual mystery in a good balance. It does have a sense of closure, which The Valley of Fear does not, even though it is not part of the larger canon. It can be read apart from everything else, of course, but you really should know Holmes, in all his full glory, to appreciate his struggles in this book.
Summary
So, here's my recommendations:
- The Adventures of Sherlock Holmes and The Memoirs of Sherlock Holmes, in no particular order. Mix and match from the two as you wish.
- A Study in Scarlet and The Sign of Four - again, in no real order.
- The Return of Sherlock Holmes
- His Last Bow and The Case-Book of Sherlock Holmes, in any order.
- The Valley of Fear
- The Hound of the Baskervilles
This is somewhat chronological - which makes some sense; I think Doyle's best work was at the beginning.