Right, that first lopping of higher level feats reduces the initial amount available. Then for purposes of Pathfinder Intro set you come along and further reduce the number of feats available by only including ones that are "frequently" taking.
As mentioned in the post you quoted but trimmed, that further culling of feats is a bit more subjective as to which are used most frequently, but I think you can whittle the list of feats available in an intro game pretty quickly.
So I am saying eliminate the level requirement feats, but don't stop there in trimming the list down.
I would be inclined to get rid of virtually all the Greater feats, leaving most trees about two feats deep, plus all the Extra feats. It's also tempting to ditch Athletic, Persuaive, etc. since they take up so much space, and are less often used; sample PCs and monsters can instead simply take the much more easily remembered Skill Focus feat when appropriate. I'd also probably trim some of the more esoteric feats like Step Up and Channel Smite. Quicken Spell is obviously gone, assuming a level 6 cap. The feat list doesn't have to be tiny, in any case, just removed of confusing and extraneous information. I might take off Arcane Armor Proficiency and not include any references to multiclassing in the basic set; too bad for bards in medium armor, I suppose.
I might consider removing Combat Expertise and all its constituent parts, if I also remove the Monk. If I remove the Monk, I keep Improved Unarmed Strike and Deflect Arrows but remove the rest of the unarmed feats.
The spell lists would require more judicious pruning.
Races:
Human
Dwarf
Elf
Halfling (LOTR appeal, you know)
Classes:
Fighter
Cleric (limited to only some of the domains, and removing any explicit references to specific deities; you pick two domains, basically)
Rogue
Wizard (Universalist, with maybe Illusionists and Necromaners as well)
Sorcerer (Arcane, plus Fey, Infernal only, I think)
I'd also be tempted to include the Cavalier and the Witch, actually. Neither requires a lot of supporting rules, and both are pretty classic archetypes.
Not to include
Paladin: Overlaps with fighter and cleric, smite is medium complicated, most of the high-payoff abilities are higher level, not having to mess with divine bond
Barbarian: It's not awesome, but you could play a Fighter as though he were a barbarian, also rage is medium complicated
Ranger: Complicated.
Bard: Bard music is interesting, but not ideal for new players.
Oracle: Most of the oracle curses involve special conditions and qualities, eg. darkvision, blindsense, etc.
Alchemist: Um, yeah. "Hi, I'm a caster with 'chemical rage' who makes you learn splash weapon rules."
Monk: Less vital archetype, fairly challenging, leans on many feats you might not want to emphasize.
Druid: Animal companions are medium complicated.