Part of the problem with Perception is how ubiquitous the idea of 'noticing stuff' is. That's a way bigger catch-all than any of the other skills. It sounds, to me anyway, like more of an ability or even game mechanic than a skill - at least when set next to the other skills. This big idea encompasses elements that might reasonably be described as being related to dexterity and intelligence as well as wisdom. So maybe make it not a skill and not tied to one stat. Dexterity already plays in to initiative, and doesn't need to be more important than it already is. But maybe a character's roll to 'notice stuff' could just be WIS plus INT mods with a DC target. No proficiency, no expertise, just the stat mods. The skill check leftovers can be covered with investigation and maybe insight.
I've definitely had that same thought, of making Perception just like Initiative -- a function of pure ability score, with only the occasional special ability or feat that would modify it. Or, classes could grant proficiency in Perception or Initiative the way they do saving throws. (I'd give Perception proficiency to elves, bards, rangers, and rogues; and Initiative proficiency to fighters, monks, rangers, and rogues.)
A similar wacky idea would be to make Perception only passive. Call it your "Perception DC," set it to 8 + Wis + Proficiency, and use it only to avoid getting ganked by ambushers, hidden creatures, or traps. Actively scanning would be Investigation or Insight. (One problem with removing the proficiency bonus from Perception is that it overpowers Stealth, which is why I included it in the DC.)