The scene taking place in the future in Excellent Adventure. Especially the reactions of the people there, getting to see their idols, the men that shaped their culture, in the flesh...the smiles on The Three Most Important People in the World is what really does it.
Really, it's rather heartwarming to discover that in the future, the entire universe has finally managed to let go of their petty squabbles to embrace a simple philosophy of altruism and living life to the fullest. Bill and Ted aren't only beloved for their music, but for being genuinely nice guys;
When Ted apparently gets stabbed (he was in armor, rolled down the stairwell, and landed in front of a real knight), Bill runs to him, begs him, "Don't be dead, dude", and attacks the guy who stabbed him in a berserk rage...and then Ted saves him (he fell out of his armor). The two hug, but then step back after realizing what they did. It's a really nice moment that really shows their friendship.
A small one, but when Beethoven at the mall is first shown the electronic synthesizer. The look of amazement on his face when the clerk turns the music on, followed by his sheer joy in playing along with it, is something to see. It even becomes a Crowning Moment of Awesome by the end of his amazing performance, but the start is especially poignant when coupled with the Reality Subtext of Beethoven having lost his hearing while still writing music. The fact he could hear this implies he hadn't lost it yet (so his seeming inattention during his kidnapping by the boys was simply being lost in his music), so it was quite something seeing him enjoy the new kind of instrument and music production while he still had the chance. The only way it could have been better is if they'd shown him getting to hear his own work that he hadn't yet written, the work he wrote while deaf.
Ever notice that Bill and Ted finally learn to get the names of the historical figures right during their presentation? "So-crates" is properly Socrates, Beethoven is not "Beeth-oven", and they demonstrate that, yes, they really can learn when they put their minds to it.
At the end of Bogus Journey, the guys introduce their infant sons to the Battle of the Bands audience. Bill's son is named Ted, and Ted's son is named Bill. It really just emphasizes the fact that these two are as close as brothers.