I know the first movie more or less runs on Rule of Funny, but still, how did the writers ever expect their notion of time travel to work? Rufus has to travel to the past to help the guys pass their history report to save the future... that presumably wouldn't exist without them having passed their history report in the first place. The writers didn't even try to come up with some valid reason why the timeline goes askew, it just does. I saw this movie when it first came out in the theater, and even at age ten or so I still thought this was bullshit. The second movie at least has a viable villain to explain the timeline change.
In the movie just after they had Deacon watch over Napoleon, Teds Dad was determined to send Ted to Oates Military accademy. He told Ted that he wasn't to leave the house until after the report. That was probably why the three most important people sent Rufus to intervene. No report = no band.
Bill & Ted has an unchangeable timeline. Rufus went back to the past to start the chain of events that leads to the utopia he lives in. He always was the one to do it, and he always succeeded in doing it.
That still doesn't answer the question though. Assuming you're right, there are at least two possibilities for what happened in the very first iteration of the timeline: (1) B&T pass their history test without Rufus' help, thus raising the question of why Rufus needed to go back in the first place; or (2) B&T fail their test, but still manage to stay together and form Wyld Stallyns despite the setback, which again raises the question above. At the very beginning, one or the other had to happen in order to create the utopian future that Rufus is supposed to protect, so why does he have to be involved at all? The only way your theory can work is if the time loop has been going on, unending, since the beginning of time itself; otherwise it had to start somewhere. And anyway, even assuming you're right, doesn't that remove any sense of urgency from the movie? No matter what happens, B&T are going to succeed; they can't not succeed, so why should the audience care? (I hope this is making sense and I'm not talking out my ass. Needless to say I still love the movies despite all this blathering, or else I wouldn't be blathering in the first place.)
It's a Stable Time Loop. The utopia Rufus comes from exists because he went back in time and helped the heroes pass the test. The suspense comes from the fact that the audience doesn't know this yet.
If they failed, Ted's father was going to send him to an Alaskan military school. They never would have formed Wyld Stallions. There is no Wyld Stallions music to inspire the world. No utopian future. I believe that was the logic spelled out by Rufus at the beginning of the movie.
That was spelled out at the beginning of the movie which is pretty much why the question was asked. If Rufus was able to come from a utopian future to save the utopian future... then that future came to be. The threat to the future was the presentation, so as someone has already pointed out, either they could have passed it without Rufus (and did, making Rufus's future even possible for him to leave) or they were able to influence the world even after they failed. Rufus COULD have come from a dystopian future that somehow figured out they could have averted the misery by having Wyld Stallyns pass, thus giving him a mission to change the future... but having coming back to preserve a past that already happened makes little sense. Another way could be for another time traveler to knock Bill & Ted off course, so Rufus has to fix it. Otherwise, this cycle of Rufus saving the presentation has never been and will never be in danger because there is no other outcome... and makes one curious how it started. It also necessarily removes suspense. Rufus having the life he wants to protect = succeeds in protecting it. The audience can see he succeeds in the first cycle of time loop because he knew the outcome of his success.
The second movie mentions a "field trip to Babylon", which means that time travel for educational purposes is common. It is possible that time travel to see the past life of Bill and Ted happened, in the process they realized that the test was tantamount and decided to make sure not only that they passed it but that they learn a lot from historical figures in the process thus making their future world leaders wiser in the process.
There is no "first iteration of the timeline". Bill & Ted pass History with the help of Rufus, leading them to creating the utopian future, where people can look at history and see that Bill & Ted needed help from a time traveler named Rufus, so they send Rufus back to be that time traveler. It's the same principle as Bill & Ted saying that, after they defeat De Nomolos, they'll go back in time and rig up the traps that let them defeat De Nomolos.
Who says that the very first time-line was utopian? Or maybe they just barely passed it by extreme studying and just barely made a utopia. The people from one line in the future saw that it was way too close to leave to 'chance' and decided to intervene. And we get maybe the tenth or the seventh or even the second time.
Or maybe De Nomolos snuck back from Wyld Stallyns-Utopia and, in a first attempt to change the past in his favor, anonymously arranged for the pair of them to win concert tickets on the night when, in the original time-travel-free timeline, they'd finally buckled down and written their history reports. They go to the concert instead, putting history in peril and necessitating Rufus's intervention.
None of these arguments can change the fact that any hypothetical Rufus-free timeline could never work. Why not? Because Rufus informs them at the end that the two medieval-era princesses were also in the band. Even if the boys had passed their history test on their own, Wyld Stallyns would still be missing its keyboardist and drummer without Rufus's help.
This, again, assumes the Princesses were always in the band. Maybe in the timeline where they didn't time-travel or Rufus didn't rescue the princesses, Bill and Ted just went through a revolving cast of backup bands (who of course went on to have awesome careers because of formerly working with Wyld Stallyns), and it's just on this particular iteration that the girls got added to the band and thus, by Rufus' reckoning, always have been.
It's possible that the utopia was created through iterations of timeline changing, not through one journey. In that first future, Bill and Ted may have been obscure musicians who showed untapped promise before their breakup.
Some old beardy guy whose name starts with an R finds an old recording of them and thinks "Man these guys are actually kinda neat, wonder what would've happened if they hit it big?" and decides to use his recently-invented time machine to go back and score them some promotion. Goes back to his own time and finds it massively improved. "Wait, what?" Hops back in the time machine, goes back, coaches Bill & Ted some more, gets them a spot at Battle of the Bands, goes back to his time, it's even better. "... Oh neat!"
Presumably, the time machine could have taken any form since it starts out as a fairly abstract-looking crystalline structure made out of gold or brass or something. So... why a phone booth, which would have stood out in just about every time period save maybe a twenty-year span with 1988 right in the middle (if that makes any sense)? Why not, say, a tree or a rock? And worse yet, why does nobody comment on it?
Well most of the time they only land for a few moments, hardly long enough for people to pay enough attention. Besides the writers/producers/ director needed a vessel that could fit almost ten people.
It got busted in their first trip through time so it's likely that it was unable to change shape. Very much like the TARDIS from Doctor Who. As for people reacting to it, the cavemen were freaking out when they saw it but otherwise, it seemed like it was usually more or less out of the way.
It needed to be something simple enough for Bill and Ted to wrap their heads around.
In the sequel the Phone Booth is changed from its 80's design to look more like an early 90's model with a more streamlined and futuristic (not to mention retractable) antenna, so presumably it can change its appearance (but apparently not its size or mass to accommodate more passengers) to blend it more, it just doesn't because Rule of Cool.
Also keep in mind that by the time Rufus' future comes about the image of the phone booth along with Bill and Ted themselves will have moved on into legend. It's an odd case predestination paradox.
