I am a huge fan of Lovecraft, and many of his stories do need to be read more than once because there are many things that you might miss. His writing style does take some getting used to, it took me while to get used to his writing but I did and I can read his stuff alot faster. My mother has tried reading his work on several occasions and she just can't read his work, she described his writing style as "ponderous" and does desribe his writing. I wouldn't describe Lovecraft's work necessarily as just horror, I would place it in the macbre category.
Lovecraft does introduce characters but he only gives a small amount of detail because he wants you see through the characters eyes. When I read his work I see myself in the character's place and really makes alot more sense if you think like that.
The creatures, not the Mythos Deities, Lovecraft wrote about are incredibly detailed. Not just by appearance but he also describes their attitude towards humans, other beings and even the Mythos Deities. Lovecraft says that many of these creatures are not evil, but because of Man's ignorance to the things around him, and the creature's own perception of what is right, Man sees these things as evil. My number one favorite story Lovecraft wrote is "The Shadow Out of Time", "At the Mountians of Madness" being second.
In "The Shadow Out of Time" a man has his mind swapped with another being, but as the being has his body in the present, the man's mind is sent to the being's body which is billions of years in the past. The beings known as "The great race of Yith" or yithian are beings that gather knowledge from all across time and space, and they do so by switching minds with the target. After they have finished gathering information they and the switched mind return back to their body. There are a few who switch minds to avoid death and the yithians treat the switched mind with great hospitality, because that is considered a taboo of sorts. They do make mass migrations of minds to avoid extinction, but they only switch minds with non-sentient beings (that can manipulate their enviroment) during those migrations. These beings seem to be the most benign in the Mythos.