Either Windows 95 or NT would be my guess...with NT came NTFS which supported long filenames (and spaces) from the start.
If I remember correctly 95, being DOS/FAT32-based, added some kind of extension to the FAT32 specification to be able to use long filenames too, but everything was still accessible through 8.3 names (first 6 characters plus tilde plus a number, usually 1 as in C:\PROGRA~1). Even NTFS still creates 8.3 names but that can be disabled for a tiny performance boost.
Anyway, I don't think the whole "Program Files" thing was around in Win3.1/3.11 days...Interesting question, though