Almost human, with a variety of fiendish traits.
Before D&D 4th edition, tieflings were simply the descendents of humans and evil extraplanar beings, such as demons or devils. 4e retconned them to be humans who had acquired devil-like features in a pact for power with Asmodeus.
When tieflings were introduced in AD&D 2nd edition, they were originally humans with a mysterious fraction of otherplanar ancestry. This was implied to be that of a demon or devil, but it was not explicitly stated, and most tieflings were wanderers and orphans who did not know their own ancestry. The Planescape Campaign Setting (1994) describes them thus:
A shadow of knife-edge in their face, a little too much fire in their eyes, a scent of ash in their presence – all these things and more describe a tiefling. No planar would mistake a tiefling for a human, and most primes make the mistake only once.
The Planewalker's Handbook (1996) expounded on their origins, and gave the tieflings a variety of traits:
Obviously human and "something-else" crossbreeds, the "somethinge-else" in the tieflings' case is usually lower-planar ...
Because of their varied backgrounds, it's possible, and even likely, that not all tieflings possess the same innate powers and appearances ... To randomly generate special physical characteristics, roll on the "Tiefling Appearance" table 1d4 times for each newly created tiefling player character.
Examples of traits include fangs, small horns, pointed teeth, unusually colored hair, eyes or skin; a tail, goatlike legs, small feathers, spiny ridges, or fur. In other words, they were humans who had some feature normally associated with their ancestor, who was a demon, devil or similar evil outsider.
Tieflings in 3e were described in the 3.5 Monster Manual (p.210) as appearing very human:
This being looks like a human, but it has a faintly disturbing demeanor about it and a wicked gleam in its eyes. Short horns sprout from its forehead. ...
Aside from a demeanor that many find disturbing, many tieflings are indistinguishable from humans. Others have small horns, pointed teeth, red eyes, a whiff of brimstone about them, or even cloven feet. No two tieflings are the same.
In other words, tieflings prior to being "claimed" by Asmodeus generally looked human, enough so to pass for human at a glance, but closer examination would reveal some trait like small horns or red eyes. Many looked sufficiently human to even pass as human.