Author Appeal: An episode revolved around going back in time to meet the Venus de Milo (she of the armless statue). The real Venus de Milo had bodybuilder-level muscular arms. She spent a lot of time flexing, with closeups, and performing various feats of strength.
Either/Or Title: Season 1 episode "The Birth of Rock And Roll, or: Too Hip For The Womb." The episode featured rock legend Little Richard in an Ink-Suit Actor role. He even furnished his voice for the episode.
Rufus: I had been selected for a most important journey. I was to help fulfill the destiny of the two Great Ones...Bill and Ted.
Milholland Relationship Moment: The titular heroes once broke a vase and went through great lengths to replace it before Bill's parents (father and stepmother to be precise) found out. They did get a replacement vase but ended up breaking it and Bill's stepmother showed up soon after. She then told the boys the vase was just some free prize they got at some restaurant. (Basically how the boys got the replacement vase in the first place).
The Other Darrin: New actors (Chris Kennedy and Evan Richards, and a third actor) replaced the voices of Keanu Reeves, Alex Winter and George Carlin for the second season due to the different cast used for the similarly named live action Fox TV show.
Refugee from TV Land: There's an episode where the booth is used to retrieve a character from a TV show. As a result, the show never ends and nothing else can ever be shown on TV, so they have to put them back.
Retool: Its second season saw a Channel Hop from CBS to Fox and a transformation into more of a tie-in for Fox's live-action series of the same name, with the original voice actors (Winters, Reeves and Carlin) replaced by The Other Darrin actors from the live-action series.
Take That: "The Birth Of Rock And Roll, or: Too Hip For The Womb" featured a veiled Take That to New Kids on the Block, who had their own cartoon show on ABC that same season. (Ironically, DiC Entertainment, which produced the New Kids On The Block cartoon, would take over the production for the second season of this show.) Bill and Ted meet Rufus at a record store:
Rufus: I was just checking out this new album by New Boys On The Corner.
Who's on First?: An episode had the boys looking for Mark Twain. They find Sam Clemens on a riverboat, shouting "Mark twain!", causing them to ask "Where?!" Clemens explains what the term means, but the next time he gives out the call, they again ask "Where?!"
Your Tomcat Is Pregnant: One episode featured a rare bird that met its demise (or else escaped) while under the care of our intrepid heroes, causing them to scramble for a replacement. Thanks to their time-travelling phone booth they manage to snag one from its country of origin, with a twist. The original was a male bird. The replacement was a female bird. This is discovered when she lays an egg.