Always hated The Phantom Menace as a title. It doesn't have that Star Wars feel to it.
Attack of the Clones is okay, but it contradicts the film.
Revenge of the Sith is my favorite of the prequel titles. In fact, I like it more than Return of the Jedi, title-wise.
My title ideas
Episode I: The Chosen, The Beginning, The Sith Revealed
Episode II: Rise of the Clones, Shroud of the Dark Side, The Clone War
Episode III: I think it should be kept the same but if not; Rise of the Empire/Sith, Fall of the Republic/Jedi