In the original time line, star ships were mainly about discovery with minor fighting capabilities.
Nero's ship and it's encounter with the Kelvin changed that dynamic.
So it's not George Kirk's death that had the profound impact on the time line so much as it was the encounter with a ship with massive destructive capabilities.
My reasoning for this answer:
It's mentioned in the movie that Captain Pike did his dissertation on that event (something else that would have been different from the original time line), which would have been read and considered by the higher ups in Star Fleet.
Addressing other questions in the OP
Whose death on the Kelvin lead to Spock starting a romantic relationship with Uhura?
Star Fleet Academy would have been different considering their assumed switch in the new time line to having a larger focus on offense/defense. Though those differences are never flat-out stated, it's a safe assumption that they lead to Spock and Uhura having a closer relationship during the Academy (Her ordering him to put her on the enterprise and him complying implied an interesting dynamic).
What event lead to Admiral Marcus finding Kahn and his crewmates instead of Kirk and the Enterprise?
I think this is the most interesting spin-off in the new time line. Again going with my assumption that the Kelvin's encounter changed the entire mindset of Star Fleet, Marcus was probably working on top-secret wartime applications before the escalating issues with the Klingons. The dock where he was building his secret ship behind Jupiter would have taken years to build, so it's extremely possible that he was already in search of new ways for star fleet to become a stronger militaristic presence and most likely already had a secret team of ships exploring the galaxy looking for the next great leap in weapons technology. My educated guess is one of them stumbled on Kahn's ship.