Sorry I haven't posted in a while on here. I've had some problems logging in. These are all very good answers and unique insight into what might have been. Here is what I think would have happened if TPM had been made first:
Firstly, the character Darth Maul would have been extremely popular and would not have "died" in TPM (I use parentheses because Maul somehow survived being cut in half and resurfaced in the Clone Wars tv show). In fact I believe Maul would have carried over into all three films, replacing Vader and the central villain. There would never have been a General Grievious and there might not have been a Count Dooku. TPM might have focused more on Maul's back story, or at least spent a good 15 to 20 min. covering it.
There would probably not have been any battle droids, or if there were they would not look the same as they did in the 99 version because it would have been very hard (or costly) to pull off back then using the budget ANH had. For similar reasons, I don't see Yoda being in the first movie as well as any aliens. Instead of battle droids, I see something to the effect of aliens. In fact the trilogy might have had a similar theme to the New Jedi Order series.
If the first movie had been successful enough to warrant a sequel (or sequels), here's how I see the sequels being different:
The character of Boba Fett would defiantly have had a stronger impact on the franchise and he would be more of a main character. He might have even have sided alongside with the rebels, thereby making him into a hero. It's possible that if TPM was made first, he and Han Solo would have merged into one character.
Now for the most important change I see happening... the end of Revenge of the Sith would have HUGE backlash among Star Wars fans because up until this point Anakin has been the hero of the series. I think that Anakin would have made an even more popular character than Luke was, because the audience would have had the opportunity to follow him literally from childhood to the point he became a Jedi. If PM and AOTC were successful I could easily see Anakin shirts, lunchboxes and even cartoon series with his likeness. Lucus would be under TREMENDOUS pressure not to have Anakin turn to the darkside and in fact we might have never gotten a Darth Vader in the series. If we had, there is no doubt that the hate for the character would be unimaginable, perhaps even sinking into Jar Jar levels. Fans would absolutely crap all over this decision and many would feel betrayed. Not to mention ROTS was overall more darker in tone than any of the previous films, so there is a possibility that sponsors would have pulled out advertising for the movie (remember what happened with Batman Returns?) This movie would either take the franchise to new heights or completely destroy it.
Lastly, if the former is true and fans were just dying for more, this series defiantly would not take as long to make. After Anakin turns to the darkside, fans would want to know what happens next and Lucus would be under tremendous pressure to make more of those movies. I defiantly don't think they would have waited 16 years for episode 4, and in fact I think we might have had all 6 movies by 1990. In fact if (and admittedly this is a very big if) the series became the phenomenon that it is today, it's entirely possible we would have seen the lost 7 8 and 9 that Lucas was talking about while in production of the original trilogy.