I never had a problem with The Phantom Menace actually. Attack of the Clones never grew on me, so i would try to change that.

It's really hard, because honestly, Attack of the Clones is the most functional title, but yet I hate it. Rise of the Dark Side could work for that one, because in a way it is the rise of the dark side... Just trying to avoid Sith.

And I guess I would call the third prequel Fall of the Jedi. I know you were trying to avoid "of the", but I didn't know how to get around it.