"PC couldn't be bothered to walk, so he/she just randomly teleported with no reasonable explanation as to how this is possible"
This is my biggest problem with people's complaints against fast travel.
It is not random teleporting. It is fast traveling. It is as though you are watching a movie and there's a "fade to black" sequence, that then fades in with the character(s) in a new location. When watching that movie, you wouldn't say "HOW DID THEY JUST RANDOMLY TELEPORT?!" you would acknowledge that they took the time to get there by walking/driving/flying/etc and the movie merely spared the viewers from having to watch hours of traveling. Fast travel is that fade-out/fade-in moment. You have to use your imagination to tell yourself that your character merely made the trip back to where ever it was he/she was going without any noteworthy incident. Time passes the same way when you fast travel as if you had made the trip manually.
It's the same as using the "Wait" feature. Your character isn't just standing there with a blank expression for an hour or more. Just imagine that he/she is sitting down, taking a drink, getting a snack, bandaging wounds, etc.
All it takes is a teeny tiny bit of imagination and suspension of disbelief and you're good to go. I never heard anyone complain that, when paying for a Silt Strider service in Morrowind, that the player suddenly teleported to a different area of Vvardenfell.