In my prequels, there would be no Yoda at all (in order to preserve Yoda's appearance in ESB), he would just mysteriously vanishing, leaving behind a vague message that he wasn't physically strong enough to fight the coming Sith; and thereby justifying Obi-Wan's decision to take on Anakin's training himself.
Obi-Wan would be a little older--not a young Jedi Knight, or even a padawaan. Right off the bat, he'd have a student...Darth Vader before he finds Anakin.
Mandalores will be the main enemy, but the Sith would have an integral part in their battles, aiding them, using them for their own ends. There could still be battledroids and destroyer droids, used by the Mandalores since they're short on manpower and depend on technology to make up for their lack of living soldiers, which then gives us the impetus for their invasion on Alderaan (that's right, I said Alderaan, not Naboo), which has ancient, but banned, cloning technology.
Palpatine would be placed into power within the first Episode; or even Chancellor/President already! (and he wouldn't be from Alderaan, an entirely other planet, an innocuous planet, he would appear as if he was the puppet, he was being used by other senators, but in fact, was using them in his greater scheme. He would keep Jedi away from the senatorial proceedings, even claiming that their Jedi mind tricks would influence senators).
As for the Jedi, the Force is not with them. No new Jedi potentials have emerged in the last decade or so (in fact, Vader would be the last known Jedi-in-training). So, the Jedi are desperate to fill their dwindling ranks (which are slowly being picked off by Sith and other enemies of the Knights). So, finding Anakin is a big deal!