Voadam
Legend
Corinth said:Take a mundane woman. Clothe her appropriately for her age, status and location. Add just one small detail that places her as other than human--use that Uncanny Valley to effect--and do so while adhering to known mythology about demoniacally-tainted bloodlines. (By default, we are speaking of Abrahamic tradition, so we shall concentrate on features such as unnatural eye color, fingers that appear to be functional as claws or talons, tail-like growths at the base of the spine, etc.). Done and done; it's not nearly as hard or implausible as you imply.
Actually I'm talking about a default 4e tiefling with the giant horns from what I've seen so far, not one with one small detail that's different from other humans. And from what I can tell they are from a decadent devil pacting high fantasy empire.
Warlock in such a culture would not be the downtrodden peasant witch status but full out fantasy sorceress by default I would think. Conan style artwork seems an appropriate starting place as does Moorcockian Melnibonean influences. Both give me more of a fantasy than realism default image in my mind.