I think the prequel titles are just fine. I don't really like Attack of the Clones, not because of the cheesiness, but because the Clones don't exactely attack. Revenge of the Sith sounds the most Star Wars like, even though the actual revenge is only alluded to.

I like Return of the Jedi much better than Revenge of the Jedi, and think it was a good call by Lucas. The title actually works in two ways: Luke is returning to the war as a Jedi, and with the Sith destroyed at the end of the movie, the Jedi order can return to the Galaxy. You could also even interpret the title being about Darth Vader: after he has turned away from the Dark Side, the Jedi Anakin has returned.