The tieflings I met are just a lot of poor people with horns.
And that is exactly what the problem is. They are not, or the very least they are not supposed to be "just ordinary people with horns". They are an entirely different species. This over humanization of them is exactly what destroys the importance of race in this game. Elves are just humans with pointy ears, halflings are just short humans, dwarves are just miner-vikings etc. This is not a good thing. Races should be radically different, and simply making them LOOK different is utterly meaningless. It's like reducing someone to how they look on the outside. Race should carry more meaning than that, especially in a medieval setting where mass literacy and education isn't a thing, so people can't be expected to know that they don't stand face to face with an actual devil (because let's face it they look like devils, they are related to devils, and assuming that they are just like you is absolutely unfounded). If you want to sell me on the idea that tieflings are "just people", then make them a subrace of humans, otherwise I'm not interested in continuing this discussion.
Also rest assured, I'm not interested in playing paladins, more of a rogue type of guy over here.
you want to be careful calling this a medieval setting, it's a pastiche of eras ranging from Imperial Rome to the Renaissance. There's also the question of what exactly a Tiefling is that doesn't seem to be clear anymore. I'm a 3e hack so to me they've always been normal people who through a quirk of birth have a very faint reflection of an Outsider in their blood, now that they've been made their own race I'm not really sure where Tieflings come from or where new Tieflings come from. For better or worse most areas we play in the FR are pretty cosmopolitan, even the rural areas don't think elves and demons are mythological creatures (though they might have strange ideas about them).
As for the homogenization of the near-human races, I think this is more apparent mechanically than narratively, but I hardly have my ear to the ground in terms of the standard D&D setting.
