I almost posted this in its own thread, but this seems like a more appropriate place at the moment.
Is Perception the oddball skill that shouldn't be based on an ability score? You look at stories, literature, movies, and you see heroes of all sorts that are perceptive in various ways. A gambler rogue may not be wise with his coin, but can spot a cheater from a mile away because he knows what he's looking for. A guardian warrior may not have the priestly wisdom, but could still have naturally keen hearing, such that he can identify the unsheathing of an assassin's dagger in a crowded room. A wizard need not be wise to notice the magical trap the rogue is about to trigger, and shout out a warning to him.
Perhaps wisdom and perception could be divorced. Some systems approach Perception as an ability score of its own, though I'm not too fond of that approach either, as I think a dwarf spelunker, a halfling swindler, and a high elf wizard might be perceptive in different areas relating to their expertise, while an urban human cloistered priest might be the least observant member in his party despite a high wisdom (though he might be the only one to spot an inaccurate spelling of Yeenoghu in a wall writing that points to a double entendre).
Perhaps one approach is removing the skill altogether. A wizard uses Arcana to perceive magical wards, a rogue detects mechanical traps with his Thievery, a fighter perceives threats in a crowd with his Streetwise, a dwarf notices hazards with his dungeoneering, etc. In 3e and 4e, Spot/Listen/Perception have been the most used and most valued skills, because it works on everything, and is used every adventure. Why not just let everyone be good at it, except, they are only good at it when it relates to their area of expertise? This way we can hopefully avoid the situation where the cleric is better at detecting traps, than the rogue, and the ranger is better at detecting magical wards than the wizard.
If someone wants to really go the extra mile in Perception, perhaps "Perceptive" could be a trait/feat/what have you, and whenever the individual is making a check to perceive using a trained skill, he could roll with advantage (whatever the final mechanic for that turns out to be, double rolls, or +2).
I think other than Perception, the 5e approach to skills seems quite good. Let's say I am trained in streetwise. I want to tail a suspect in the crowds without being seen, I make a dexterity check and add my streetwise. This would reflect my ability to keep the target in sight, and use passing wagons and carts to my advantage to not be noticed. I want to use my knowledge of the streets to come up with a shortcut, I make an intelligence check and add my streetwise. I want to gather information about a local vigilante, I make a charisma check and add my streetwise. This allows skills to reflect what a character is truly good at. So my fighter trained in streetwise doesn't need to be trained in "stealth" to tail someone in a city, and doesn't need to be trained in "knowledge local" to know a few short cuts around town. I think being trained should be a +5 rather than a +3, so training has a greater impact than natural talent, but that's just a numbers game.