Part 1 didn't have them making the song, just needing to pass that history class to ensure they would make the song in the future (since failing the class would cause them to seperate). Bogus adventure was a guy from the future wanting to fuck up the past to change the future, so he made robot Bill&Ted, had them murder the real Bill&Ted, then had the robots pretend to be the real Bill&Ted to alter the timeline. Bill&Ted then have to escape hell, then heaven, to come back to life and set the timeline straight.
Part 3 sounds like they just haven't been able to make the song yet, so while the "plot" is different than 1, the fact they have to time travel to find the song makes it somewhat similar to 1.