Sidious had the opportunity to replace his previous apprentices with a young, extremely powerful apprentice (Vader) by the time he was ready to issue Order 66.
Darth Maul was defeated by Obi-Wan on Naboo (and lost his position as Sidious' apprentice) before the clone army was ready, so Order 66 could not be issued while Maul was Sidious' apprentice.
Maul was replaced with Tyranus, who in his position of leadership in the Confederacy of Independent States helped foment the Clone Wars -- a conflict that was necessary to distract and set up the Jedi for mass execution by the clones. Since Order 66 was mainly carried out by the clones anyway (the attack on the Jedi Temple was only one of many simultaneous attacks on the Jedi), it didn't make much difference whether Tyranus or Vader led the attack; it would have been theoretically possible for Sidious to have Tyranus lead the attack on the Jedi Temple if Tyranus was still Sidious' apprentice by that time. However, Sidious knew he could seduce Anakin to the dark side and was able to get rid of the aging Tyranus by the time he was ready to issue Order 66.
Sidious was always looking for a more powerful apprentice -- it's the same reason why he later wanted to replace the injured and aging Vader with his son, Luke.