On preview, this post got real, real long. Looks like you got my attention, Argent Towers. 
I liked Episode III, but the prequels really disappointed me. Everyone’s brought up some really kickass ideas that got me to thinking too.
The Clone Wars
When I was in junior high around '95 a friend of mine introduced me to the EU stuff when I asked him what the Clone Wars actually were. If memory serves, it was his understanding that the Clone Wars involved great leaders, thinkers, etc. who became effectively immortal through cloning. Either as a side-effect of the procedure or because of hubris, they became evil. If Lucas had used a similar concept, calling the conflict the Clone Wars would make a lot more sense than simply having clones involved in the fighting. That would have meshed well with the direction Palpatine’s story went in the EU after the OT, and it would have made a nice backdrop for Anakin’s fall from grace.
Re: Push You Down and Anakin/Darth Vader
Not only was kid-Anakin thing worthless, but the whole plot of TPM was all but unnecessary. By AOTC the trade federation was a footnote anyway. He should have AT LEAST been a teenager, especially re: Sweetums and “Already a great pilot.” I’m also a fan of the idea that Anakin could have filled the Han Solo niche in the prequels. Everyone loves an antihero, but having one’s loose cannon antics come back to bite you in the ass would have been a nice twist on having it pay off in the end like it has in House and suchlike. The idea of a trilogy-wide peer rivalry between Anakin and Dooku ending with a question as to which one really became Darth Vader is, moreover, triple-distilled badassery. Good call, Push You Down (that was you, right?). One of the things that left the prequel trilogy so hollow was the lack of any well developed, specific rivalry like the one between Luke and Vader in the OT.
Re: dotchan and the Anakin/Padme/Obiwan love sandwich
To build on the love triangle idea, Obiwan and Padme could have faked a stillbirth or something like that after reading between the lines with Anakin’s turn. He would have sensed something was up with their scheming, but would have mistaken it for an affair. That, in addition to the loss of his “only” child would have pushed Anakin that much closer to the Dark Side. I’m thinking Palpatine could have exploited that a lot more effectively and sympathetically than appealing to some ill-conceived teen angst. Then, by the time Anakin and Dooku fight for the last time, Anakin’s not fighting to stop the Sith, he’s taking out all his frustrations on some fucker who’d been giving him trouble throughout the whole story until that point.
And to add to the confusion over Darth Vader’s identity, at the end each member of the “triangle” would have thought the other two were dead, with Padme and Obiwan each having independently faked their own death. We wouldn’t have to come up with contrived reasons as to why Leia remembers her mother being “sad,” since Padme would have had to live with the fact that 1.) protecting her children ended up pushing Anakin over to the Dark Side, 2.) as far as she knew he was dead, and 3.) she had to give up one of her kids.
Other stuff people have said
And while I wouldn’t have necessarily been opposed to the idea of having some backstory for characters from the OT and outside of the Skywalker family, I don’t like it when all the central characters have “actually” had some pivotal role in history before, say, showing up as a copilot on a smuggler ship on some barren sandheap. Having Chewbacca and Yoda be old war buddies was bullshit (although having him show up in the battle on Kashyyk was cool). I agree that Bail Organa should have had a more prominent role, and Mon Mothma definitely should have had a bigger part than a cameo in a scene that was ultimately cut. Likewise with Uncle Owen, Tarkin, and others like Akbar and Veers, as others have suggested. I’ve got a couple of ideas:
Tarkin could have showed up as a commander in the army of the Republic with strict methods that would evolve into his brutal methods later. Anakin would still have been good at the time, creating a grudge that would have persisted even though they eventually came to see eye-to-eye.
While Palpatine is announcing the consolidation of the Empire it cuts to a scene on Corellia where a 10 year old Han Solo is playing Stormtrooper or something with his friends, wishing he was old enough to enlist.
Like vibrotronica suggested, Anakin wouldn’t have been from Tatooine. I’d have made Owen his cousin or half-brother and kept his background as a slave. That way they’d have relied on each other working to earn their freedom, but started to disagree and drift apart afterward. Owen would have only wanted to make a decent living, but Anakin’s involvement with the Clone Wars and the Jedi dragged him in. Owen would have taken Luke in out of a sense of duty to Anakin, but resented Obiwan and the Jedi because he had to give up what he had and go into exile on Tatooine too.
