I'm not such a big help on the Fantasy genre, but I can recommend some Murder Mysteries =] (And chime in with the "Terry Pratchett!" crowd...)
Agatha Christie - The Murder of Roger Ackroyd, Murder on the Orient Express, Peril at End House, And Then There Were None, Nemesis, Sleeping Murder.
Sir Arthur Conan Doyle - Sign of Four, Adventures of Sherlock Holmes. (I love Hound of the Baskervilles but it's sort-of painfully obvious who the culprit is from the start, so it's better read as a Gothic novel than anything else IMO, and Study in Scarlet spends half the novel on events leading up to the crime.) There's also an anthology I'm reading at the moment called "The Improbable Adventures of Sherlock Holmes", which is penned by various science fiction and fantasy authors like Stephen King and Neil Gaiman. Some of the stuff is fanboy dross, but there are stories in there that Conan Doyle would have been proud of (ahem, had he actually liked his creation, lol.)
P.D. James - The Murder Room, A Taste for Death, The Private Patient.
Stieg Larsson's "The Millennium Trilogy" are also brilliant, but the second and third are less murder novels and more an explanation of Lisbeth Salander's past. The first constitutes a good old-fashioned 'locked-room' mystery...spanning an entire island, though.