To this day I have yet to play as the villain in any of the RPGs that have the option to play as the hero or villain such as in games like KOTOR, Fable, and Fallout.

But part of me feels like in some cases it just feels "wrong" to play a bad guy because sometimes it feels like it doesn't make any sense, especially when the plot feels like it was tailor-made to play as the Hero with the villain playthrough feeling like an afterthought.

I had this feeling with Mass Effect and how the plot doesn't really make any sense to play a bad guy when the stakes feels more appropriate for a good guy.

So what RPGs actually address this? Where it actually built from the ground up to play the villain in a way that feels like it works with the plot and the gameplay?

Mass Effect had the right idea in shifting from "good/evil" to "paragon/renegade". Simply because you're not a boy scout doesn't make you evil. Unfortunately the execution is wheere they dropped the ball, and choosing a renegae path still means acting like a violent psycho or a bully. Still it's better than Andromeda, where I think it's impossible to even make the player character raise his voice. I really wanted to play it as a Captain Sisko type character - a good guy, but one who gets angry, yells at people, and gets his hands dirty. But no, the game gives you pretty much zero freedom of choice, and your character always sounds like he's on quaaludes.

Tyranny is all about being evil. I've never played evil characters in RPGs, so I'm having a lot of fun trying to avoid becoming one in this game. :)

All hail the Overlord!

Another vote for Tyranny.

Wizardry 4 has you playing as the bad guy from Wizardry 1.

One thing is that, late in the game, after you've gotten through some extremely difficult dungeon crawling and battles, the game gives you the satisfaction of slaughtering new adventurers with your greater demons and other powerful monsters.

Undertale also has its genocide route, where you kill literally everything that's killable.

I played a lot of RPGs, and I have yet to find one that makes villains compelling in any way.
I'd say the only one I can mention fitting the category is probably Mask of the Betrayer for NWN2. There you can really push evil to unseen limits.
For the rest... maybe Planescape Torment, although that would be selfishness more than outright villany.

I disagree with Overlord because it is not a RPG and it is moslty for the laughs (love both the games, though).

I disagree with Tyranny because even there you end up being far less mean than you could (and should)!
There is actually even a "heroic" way of playing it. Paladins, please.

Dungeon Keeper and Dungeon Keeper 2 as strategy games go, with RPG tropes. Admittedly not a RPG.

Yes, it is presented in a funny way but I felt like 1 did a good job about the "bad guy" thing. Under all the surface humor, the main plot is actually pretty dark. Basically a revenge quest to kill your former friends for leaving you behind/for dead. It also has some slight RPG elements (some choices, crafting armor, weapons, upgrading them etc.).

I definitely found Overlord 2 very close to the cringeworthy territory when it came to the humor and it devolved to the generic "fight greater evil" cliche.

Closest I can think of is Warcraft 3, when you play as Arthas. Of course there are only light RPG elements.

If you are looking for a different RPG experience that's still excellent, but where you aren't playing a classic hero type, and where its nigh impossible to be a goody two shoes, then have a look at https://www.gog.com/game/darkwood and https://www.gog.com/game/sunless_sea .Moreso the former than the latter.

I haven't played it myself, but Vampire: The Masquerade - Bloodlines might also be an option here.

I liked how Age of decadence did it, where everything is pretty grey morally and there are no clear lines between good and evil (even if that was a bit overdone at times). However I still felt there were "better" and "worse" options. The merchants' guild and the thieves are pretty much scumbags imo, all about greed without any ideals or any consideration of the common good. Whereas paradoxically the assassins can turn out to be one of the most morally satisfying factions imo.
In general the setting is just very brutal, a ruined world where most people just look out for themselves, so a selfish kind of evil feels quite natural (you don't have any options for gratuitous sadism or the like however, which imo keeps the evil more relatable, in a sense of "I actually might do this if I lived in this world, I wouldn't even need to be a psychopath for it").
But it looks like you're looking more for a traditional villain, and yes, that is indeed rarely done well in crpgs.

I think the big problem with getting a "evil path" right in games is the fact that pretty much all games assume actions are synonymous with intentions. You act nice, because you are nice and want to be a good guy. But a real villain would act like a good guy 90% of the time too if they have any brains. A villain will try to get people to like them, to be on their side, to trust them. Duplicity is hard to write into a "choose your own adventure" story, but without it it's hard to play compelling, smart villain.

Baldur's Gate 1/2 is very black and white in its morality, and heavily skewed towards the good side, e.g. there are fewer evil party companions in BG2 (though they're pretty fun to play with), many quests lack evil choices that make sense and you usually get heavily penalized for evil behaviour (poor rewards compared to good choices, plus you take a hit to your reputation which will lead to higher prices in shops and to being hunted down by Flaming Fist enforcers/Amnish soldiers and an eventual game over if reputation gets too low and you don't bring it up again). You can play as an evil character, but you always notice to some extent that this isn't how the games were meant to be played.
In Icewind Dale 1/2 it's largely meaningless, those games are all about combat with very limited choices anyway.
Can't comment too much on Kotor 2 and Fallout: New Vegas since I never really tried evil in them. But the main baddies in Fallout: New Vegas Caesar's legion are so over the top evil (total misogynists who keep women as sex slaves etc.) that they're hard to identify with; and they also don't have as much content in quests etc. as other factions, so joining them is regarded as unsatisfying by many players.
Kotor 2 might be more interesting, as I understand it you can actually corrupt your companions and turn them into Sith.

Fallout 1/2: tbh I'm not sure if there's a coherent answer to that, and maybe I'm misremembering things. But what annoyed me in Fallout 2 is that you can join a guild of slavers who capture tribal people to enslave them...but to join that guild (for a few slave hunting expeditions, not a major benefit) you have to get a tattoo identifying you as a slaver on your face. Which then makes you despised by lots of people and locks you out of quests. I thought that was kind of dumb...why would slavers even advertise their profession in such a manner?

Yes, this. I like playing a Dirty Harry style renegade, I don't like playing someone cruel and pure evil. Too many RPGs go with the latter for their rebel type choices. I mean nuking a city for lulz? Come on. I actually disagree with the rest of your post, I think ME 1-3 did Dirty Harry very well. There were only a couple of times I felt like it went over the top, like a moment in ME2 where you send an innocent out as a bullet shield.

Anyway... other good Dirty Harry type shoot first and ask questions later RPGs are Fallout 4 when siding with the Brotherhood of Steel and the recent Shadowrun trilogy when playing a ruthless corporate merc. I also played Outer Worlds as a ruthless corporate merc but it wasn't that satisfying.

For absolute pure evilNeverwinter Nights 2: Mask of the Betrayer is supposed to have the best pure evil storyline ever. Sadly I haven't played it that way yet, keep meaning to do that.