When I jumped into my GNU/Linux journey in late 90s, TNR was nowhere to be found, and I believe is only available through "ms-ttcorefonts" or whatever the package is called (IOW, Times New Roman actually comes from Microsoft).

I believe "Times" is the venerable standard, and has been present on Unices and Macs since... forever. Now, TNR is the same metrics-wise IIRC, and thus it was always a recommendation to use a fallback line of the form "Times New Roman, Times, serif".