Ah, I am always willing to recommend new King books
Hmm, let's see. More supernatural than horror...You could try
Insomnia -- it's not one of his earliest by any means, really, having been written in 1994, but I think it's more supernatural than horror. It also links into
The Dark Tower series in a brief way (not anything incredibly important) which I strongly suggest you read at some point (that is definitely more fantasy than horror, that series). Or, while on the subject of more fantastical,
The Eyes of the Dragon is more like a fantasy novel, quite different to most of King's work, indeed. And it also introduces you to Flagg, King's uber-villain!