Hi ManyMiles
Good topic!
I first flew on VS from EWR to LGW at end of '88 in Upper. Was seated near back of nose section. Seats were like old (early 80's) First Class seats, and indeed were advertised as such. There was also the Upper Deck and at least one other cabin on the Main Deck. Seats were in a red cloth material. I'm not sure if these seats remained in use until the J2000 seats came in in '99 or so. Later seats looked newer but didn't seem so comfy for sleeping in my opinion. Some 747s had a UC lounge with leather seats and a backgammon table! I believe this was sometimes on the Upper Deck. At least one 747 had the lounge at the front of the "B" cabin (VJFK c94?).
Mid Class was launched about '92. Was supposed to be mid way between Upper (which was itself midway between conventional J and F) and economy. It was full fare Y and was brought in during a recession when many companies (including the one I worked for) downdraded their employees from travelling J to Y. I first flew it from LHR to LAX in Oct '94. There was a letter from RB (no "S" then!) extolling the virtues of the new legrests

but explaining that it was being renamed "Premium Economy" [:(!]. With the IFE screens and legrests which were fitted to all 747s it was very much like the "lesser" business class seats of that time, Emirates, etc.
I flew on many of the 747 Classics, and there were many layouts of UC and PE fitted. Some had PE in the nose even. Some had PE in the "B" cabin. VBEE had this, with a galley in most of the centre row, with most of PE down the sides. The A343s originally had about 28 UC seats in one cabin. The second cabin had about 28 PE seats, and had it's own loo! These were reconfigured to give about 40 UC seats, and the PE section was moved back, losing it's loo to UC. Also there were no legrests on the seats, only footrests. These aircraft were used for the longest haul flights to Asia, where these deficiencies would be even more apparent.
The best of the old UC was in my opinion on the Upper Deck on the later (ex-NZ) Classics about '98-2000 with only 12 seats, very much like a private jet! BA had a similiar layout on their's when I last flew on one in '98. Second best was the nose.
Best PE was and is Upper Deck on the 744s as numerous posters will testify.
I believe that for the future VS will need to re-evaluate it's classes again, especially in the light of deeply discounted J class on other airlines including the "Worlds Favourite".