Since PF1, paladins had been charisma focused, WIS actually was a dump stat for them.
In PF2, the detect evil stuff is locked behind a feat, and I don't think you can take it until 8th level because of the level gating.
So where does your " Paladins are strong in sense motive " argument come from then? if its related to detect evil that has nothing to do with sense motive as a skill.
Skills were never icing on the cake. They're a core part of your character build that dictates what you are and are not good at aside from casting/fighting.
With the exception of rogues I have to disagree. While skills have become an intricate part of the rules, the core concept of the game (based on the original AD&D) never even had a skill system. It wasn't until 2nd edition non-weapon proficiency list came in to help flesh out characters backgrounds. This evolved into the skill system of 3rd edition. The clunky rogue "open locks/pick locks" table was the only thing that benefited from the port into a skill system.
Casting/fighting are the backbone of encounters, you couldn't "win" an encounter with skills alone unless the encounter was non-combat like negotiating a dangerous rope bridge.
Yes systems as they evolve find new ways to link skills to encounters. PF2 's use of hazards are an ingeneous way to mix skills into an encounter for example. but the skills of 3.5 where still a choice. If they where core, everyone should be able to do them all, but they can't.
Thats why people choose the ones that will get used the most over "fluff" skills and why perception has now been removed from the skill system because its "THAT" important. I mentioned before in another post about diplomacy/gather information/bluff/sense motive etc. how useful are they in a campaign set on a deserted island populated by dinosaurs? Over time fluff skills have gained combat uses (feint for example) to try and entice people to take ranks in those skills.