Corrected entry: Future Bill and Ted introduce Past Bill and Ted to Rufus. Rufus never tells them his name.
Corrected entry: One of the guys says at one point says something like "Look it's the Goodrich blimp" while looking towards the sky. This was in reference to a commercial popular in the 1980s for Goodrich tires where people would be faked out by others after being told to look up at the Goodrich blimp. The fooled one would then say "Hey, Goodrich doesn't have a blimp" after looking up and being tricked. The point was Good Year had the blimp but not Goodrich.
Correction: Hey says Goodyear, not Goodrich. Since there were obviously no blimps in the old west, the cowboys all turn to see what he's talking about.
Character mistake: In the movie they grab Genghis Khan in 1209 which would have been correct, he ruled Mongolia from 1206 to 1227. In the presentation at the end they say in 1269 he did this and that, that would have been Kublai Khan's reighn of terror in Mongolia.
Suggested correction: Bill and Ted have proven not to be that smart. Easy for them to get those things confused.
Factual error: During Bill and Ted's first time traveling in history, Rufus states they are in Austria in the year 1805. 1805 was the year Napoleon achieved his greatest victory over Tsar Alexander I and Mikhail Kutuzov at the Battle of Austerlitz (present day Czech Republic). Napoleon didn't invade Austria until 1809.
Suggested correction: Austerlitz was part of the Austrian Empire. But that battle was after the Battle of Ulm. After Ulm surrendered, Napoleon advanced to Vienna and took the city. The Austrian War did occur in 1809, but that was Austria attacking to free neighboring countries under Napoleon's rule.
Plot hole: It seems that after committing 6-odd counts of aiding and abetting, literally right in front of the strict Police Captain father of one of them, Ted and for that matter Bill, would be lucky to only go to military school, regardless of passing or failing one particular class.
Suggested correction: The threat of Ted having to go to the military academy in Alaska was because he was going to fail. Since they passed and graduated, there's no need to attend the military academy. Some time passes before Rufus brings the babes to Bill and Ted, so we don't know what punishment they were given.
This isn't ordinary misbehavior, it is a felony, what do you think the punishment would be? No TV for a week?
I don't have to speculate what their punishment would be. Certainly neither would be sent to military school (which is a TV and movie trope that wayward children get sent there anyways). Your mistake entry is not a plot hole plain and simple.
Corrected entry: In the scene where Ted falls down a spiral staircase, the stairs should spiral anti-clockwise, not clockwise. This is because in medieval times, the castle's defenders would have an easier time defending in this direction as almost all of them would have been right-handed.
Correction: This is true of most towers in castles, but some had staircases going the other way, so that if the castle was taken over, then they could have a slight advantage if they tried to recapture it.
Correction: The clockwise spiral of a newel staircase being designed that way to give defenders an advantage is a myth, one that I'm sure castle tour guides love to tell. Not only is there no documentation for this, and the direction of the staircase would not provide an advantage to the defender. In both cases, the attacker would always have the advantage (not to mention the fact that the stairs were extremely narrow and defenders would be more prone to fall down then have an advantage, as Ted demonstrates).
Correction: Also, present Bill and Ted hear their future selves introduce him as Rufus. Thus their learning his name is part of the time loop.
Vader47000