This is something I'm come to be quite interested in as a result of the intense 3E/Denner discussions of late.

This is what I can think of from official sources:
OD&D Greyhawk - Paladin
1st ed AD&D - Bard
UA AD&D - Thief-Acrobat
Companion Set D&D - Avenger, Paladin, Knight, Druid + some pretty soft & fluffy Magic-User & Thief options.

Didn't Dragonlance have you choose your color of Magic after reaching a certain level, and multiple branching Solomanic Knight classes?

Runequest's Rune Lords and Rune Priests were Prestige Class-ish as well.

Well, a lot of the 3rd Edition PrCs were themed around a specific fighting/spellcasting style or elite order of people.  Prerequisites for the classes usually involved sidequests and proving oneself to an individual/group as well.

In 1st Edition AD&D, there weren't Prestige Classes per se, although the Bard, Druid, and Monk class does have definite similarities.  Druids and Monks could not progress past a certain level unless they defeated their superior in combat.  So in order to unlock the highest-level Druid Spells or the Monk's Death Touch, you had to go on a sidequest.  And Bards were all part of a Bardic College and couldn't join unless they had Fighter/Thief/Druid training.

Yes to the Dragonlance questions.  Each progressive Knight order had more and more restrictions, while each Mage order had proscribed schools.  For instance, only Red Robes got Transmutation, Blacks couldn't use Evocation, and so on.  Runs in my mind that only Whites got Abjuration, but it's been quite a while now since I opened DLA.

Mid to late 2nd Ed., the Dark Sun setting had Dragon and Avangion classes that were fairly similar to PrCs: the character had to start as a wizard 20/psionicist 20 and then go through rituals to advance each level beyond 20th, which would get them level 10 spells and various other hideous powers.
 
Also in 2E, Planescape characters who advanced in their factions (to become 'factotums') gained extra special abilities, but I think that was a thing that involved mainly quests/DM fiat rather than level advancement.
 
Most things that were PrCs in 3E were just kits in 2E, so you'd start as a pirate or gladiator or bandit or whatever at 1st level, instead of needing a quest mid-campaign to qualify. Also more convenient when trying to write a backstory.