BadDecissions: And following in Crowned's steps, I'll recommend a related non-Lovecraft story, "The Willows" by Algernon Blackwood; Lovecraft called it the best weird story every written, and he may well have been right.
Now that Blackwood was mentioned, I also recommend "Wendigo". Most of us know the supernatural entity already, but this take on it is an early one, and also differs from today's mainstream view.
Also very glad to see the King in Yellow being appreciated, although I must admit the first stories (the proper King in Yellow ones) were the best in that one. There were great moments in the latter ones as well, though, particularly interesting to me was "The Street of the First Shell, if I remember correctly.
And of course the Poet's Paradise, it was such a mysterious piece.
"If but the Vine and Love Abjuring Band
Are in the Prophets' Paradise to stand,
Alack, I doubt the Prophets' Paradise,
Were empty as the hollow of one's hand."
Aand I did not remember that from the top of my head, sadly. : D