Neat idea. Here are my three:
Grapple (Dex/Str)
This is a hard sell. Grapple checks already grow with the BAB, so making a skill out of this mechanic seems flawed at first. Imagine the monk, however. At 20th level, a monk's BAB is 5 behind his HD where his max ranks are 3 above it. That's an 8 point difference. Even considering Improved Grapple, the difference is only halved. Take this idea into account, however, and the monk becomes the top grappler-class (as I feel it should be and fails to do as written). At full ranks, a 20th level monk has a base Grapple of +23, coupled with a descent Strength or Dexterity (this skill uses the best, unlike the current grapple rules) and Improved Grapple, their check could easily break +30. Throw on some of those crunchy Complete Warrior feats like Clever Wrestler and the monk is back in business and tossing those half-orc barbarian grapplers on their faces.
Class Skill: Fighters, monks.
Branch-ideas: A feat called Chokehold that sticks the victim of your pin with the "suffocating" condition (DMG p. 304). A feat called Submission Move that gives your Grapple check a critical threat range of 19-20 for double damage on successful Grapple checks.
Perception (Wis)
This wraps Listen, Search, and Spot (as well as the Scent special ability) into one skill. The idea isn't to make it easier for rangers and rogues to diversify their skills, but to streamline the idea of people getting more cautious with experience. Fighters just don't have the skill points to sink into Spot and Listen as it stands--and they're the ones taking lead in the party most of the time, playing the all-too important role of meatshield. Racial modifiers to certain forms of perception still come into play here. Elves, for instance, gain a +2 to Perception rolls made to see or hear something. Gnomes get a +2 to smell something, same as orc-breeds. Creatures with the Scent ability gain a racial bonus to Perception rolls made to smell things equal to their hit dice. Smelling something under this mechanic would be little different than making a Spot check. If the smelling creature cannot otherwise detect their quarry then a successful Perception roll (DC 20) will give them a general idea and an opportunity to make attacks, albeit with a 50% miss chance.
Class Skill: All.
Branch-ideas: Skill Focus (Perception) becomes a considerable option for games where surprise is a big factor. Alertness becomes moot. Quick Reconnoiter (from Complete Adventurer) is still just as cool.
Run (Con)
You can basically put ranks to the Constitution check made to avoid having to stop running. As the rules state (PHB, p. 144), a character can run for a number of rounds equal to their Constitution score, but after that they must succeed on a DC 10 Constitution check to keeo running. Each round spent running requires an additional Constitution check with a cumulative +1 to the DC.
Class Skill: Barbarians, fighters, rangers, monks.
Branch-ideas: A feat called Cross Country, allowing you to run over difficult terrain. A feat called Flight Reflex, allowing you to maintain your Dex bonus to AC while running. A feat called Marathon Run that reduces the amount of time you need to rest after finally failing a Con (or Run) check in half (5 rounds instead of 10) before running again.