There were no major changes to history because there were likely no changes whatsoever.
Bill & Ted's Excellent Adventure appears to adhere to Novikov's self-consistency principle, whereby the effects of any actions undertaken by a time traveller within their own past will already have been baked into the timeline to begin with.
The keys you mentioned are a perfect example of this. In the same scene where Ted comes up with the idea to steal his dad's keys, he remarks that those keys have already been missing for two days. He knows this because his dad told him the keys were missing in an earlier scene, and asked him if he'd done anything with them. Ted subsequently concludes that he had done something with them (i.e. stolen them)... or rather, his future self had.
Bill: How'd it go?
Ted: Bad. Our historical figures are all locked up and my dad won't let 'em out.
Bill: Can we get your dad's keys?
Ted: Could steal 'em, but he lost 'em two days ago.
Bill: If only we could go back in time to when he had 'em and steal 'em then.
Ted: Well, why can't we?
Bill: 'Cause we don't got time!
Ted: We could do it after the report!
Bill: Ted! Good thinking, dude! After the report, we'll time travel back to two days ago, steal your dad's keys, and leave 'em here!
Ted: Where?
Bill: I don't know. How about behind that sign? That way, when we get here now, they'll be waiting for us. See?!
Ted: Whoa! Yeah! So, after the report we can't forget to do this, otherwise it won't happen. But it did happen! Hey, it was me who stole my dad's keys!
Bill: Exactly, Ted! Come on!
This is a textbook case of the past being affected by a future that hadn't happened yet (from the perspective of those living in the present), and we see an even clearer example of this when Bill & Ted meet their future selves outside of the Circle K convenience store.
We first see this scene around 15 minutes into the movie, from the perspective of the slightly younger versions of Bill & Ted. Around forty minutes later, we see the same scene again, but this time from the perspective of the slightly older versions. As far as we're shown (the movie skips over part of the conversation the second time around), the two versions of the scene play out exactly the same way, just from different perspectives.
What the younger Bill & Ted saw then was essentially a preview of their own future, and not a possible future to be clear, but the actual future (from their perspective) that would definitely and verifiably happen.
Now consider everything Bill & Ted did during the roughly forty minutes of runtime between the two versions of that scene. That's the very window within which they plucked all the historical figures (Abraham Lincoln, Genghis Khan, etc) from their respective time periods, and brought them to 1988.
The fact that the younger versions of Bill & Ted were able to meet the older versions of themselves who'd already performed those actions before they (the younger Bill & Ted) subsequently went ahead and did the same thing is another strong indication that they didn't change anything by going back in time. They were just bringing things full circle, ensuring that the past unfolded the same way it already had done, which is a central feature of Novikov's self-consistency principle, and a necessity in order to avoid any grandfather paradoxes.
We get a third good example of this at the end of the movie, when Rufus brings the English princesses, Joanna and Elizabeth, to 1988. At this point, Rufus reveals that the princesses were part of the band themselves.
Rufus: Hello again, my excellent friends.
Bill: Whoa!
Rufus: Congratulations on passing your history report.
Ted: Rufus! The babes! We looked all over England for you!
Bill: Where'd you get those savory clothes?
Princess Joanna: Rufus introduced us to a place called the mall!
Princess Elizabeth: And something called credit cards!
Rufus: I got them out of England just before they had to marry those royal ugly dudes.
Ted: Oh, way to go Rufus!
Bill: How can we ever thank you, Rufus?
Rufus: Well, you can start by signing this for my kids.
Ted: Why?
Rufus: They're big fans of yours!
Bill: What?
Rufus: Everyone is. Wyld Stallyns' music has become the foundation of our whole society.
Bill & Ted (simultaneously): No way!
Rufus: Yes way! In fact, I believe you were there. That futuristic place with the domes?
Bill: And the totally excellent music!
Ted: They totally worshipped us there, Rufus!
Rufus: I know! That's why I was sent to make sure you passed your history report. If you guys were separated it would've been disastrous for life as we know it. You see, eventually, your music will help put an end to war and poverty. It will align the planets and bring them into universal harmony, allowing meaningful contact with all forms of life, from extraterrestrial beings to common household pets. And... it's excellent for dancing.
Bill: Whoa.
Rufus: Why don't you have the ladies sign as well, would you please? After all, they are in the band.
Bill: They are?
Ted: Excellent!
This again implies that their (permanent) displacement from the 15th century to the 20th and 21st centuries didn't strictly alter history. That event was already baked into the timeline all along, and part of the existing history from Rufus' perspective. He didn't come back in time to change history, but to ensure that it happened the way it was 'supposed' to, as far as the historical records of his time period were concerned.
