Here's another vote for KISS ME KATE! Saw it in previews and thought it was so much fun! An old fashioned Broadway musical. And how can it miss with a score by Cole Porter? The star, Brian Stokes Mitchell was also wonderful in RAGTIME!
Speaking of CATS (and a lot of you have mentioned it)...I think it depends on where you see it. Can't imagine it being as effective on the road as in the Wintergarden in NY...the whole theatre was redone to incorporate it. And if you're looking for plot, that's NOT the show to see. Based on a book of poems, how much plot could it have? I happen to like T.S.Eliot's poetry, so I liked the show as well. I have come to be terribly unimpressed by Sir Andrew's music of late, however. It all sounds alike. There's a satirical review of B-way shows called FORBIDDEN BROADWAY, that's been running for about 20 years, I think...(it's updated every two or three years, to include new Broadway shows). In FB Vol 2 they really let Andrew Lloyd Weber have it. And one song even refers to the "borrowing" he's been accused of. I've forgotten the beginning of the line, but it ends with, "Puccini is awfully pissed." Another good line about ALW is "Your scores pour forth a veil of melody. Just like a nightingale on LSD."