Hell yeah! A whole Mythos based CV gaiden would rock my balls.
I've actually thought of an idea similar to CV that deals with Lovecraftian mythos. My little story was called "Grimsdyke", and it takes place somewhere in British isle, in a rather large castle-like mansion that sits atop a hill, on ancient lands soaked in dark dealings. The owner of the mansion(Dracula-like fellow) is abducting people from the nearby village as to sacrifice in a dark ritual to call forth the Elder Gods and bestow a new age of darkness. Among them is the main hero's betrothed, so gives chase and enters the dark mansion with an sword(family heirloom) and pistol(enchanted) in hand, slicing and blasting his way through various lurking fears and crawling terrors. My idea, it was set in the late 1800s(you know how I feel about that time, and how I've been WANTING a new HD CV game that dealt with that era).
Now, back on topic, for what I'd love to see, considering the CV series has always been a loveletter to horror pop culture, I'd love to see some more recent horror figures appear. Leatherface already appeared in OoE, and we had nods to the Puppet Master movies with the Puppet Master boss. Maybe do a Cenobite-type monster(bondage heavy, with nails and portruding from flesh wounds, though not overtly Pinhead or any other Cenobite in any of the Hellraiser movies). Call it a Hellion or Pain Jockey(though, I prefer Hellion).
And with Ruthven, I've mentioned that there are so many real-accused vampires that could be included in the same vein as Dracula, Elizabeth Bartley(Bathory) and Gile de Rais. Clara Geisslerin, Arnold Paole, Fritz Haarman, Peter Plogojowitz, and John George Haigh. Of course, even Bram Stoker's other vampiric creation, the Countess Dolingen of Gratz.
I also thumbs up the Randall Flagg bit. Even if that name is too obvious, Randall Flagg has many different aliases that could be used.