One more important thing that hasn't been mentioned yet: The structure should have been very different. The first movie should have gone right into the life of Anakin and not show us a stupid little anakin-child all of the time. No one cares about HIM. What the audience wanted to see is the Hero that was described by Obi Wan in the OT and how he would turn into Darth Vader.

With almost the complete first movie missing I would have had much more time to develop the relationship between obi wan and anakin, to give the audience some characters to genuinly care for and a republic at stake, which Anakin fights for because he believes in something... not just because of a girl or because someone tells him to.

Obviously this would have made turning him to the darkside much more difficult for Palpatine which would have in turn required really great story telling to pull it of. The PT was a cop-out by making it the direct path for anakin. It would have been more surprising to have him refute the power of the dark side.

Of course there are many many more things i would have done differently, especially the ones that were already mentioned by some people. For example i strongly agree with these two postings.