Kristi Yamaguchi had a great program to that
Thanks, Toni! I knew I'd seen that from a skater but couldn't place it. She also did a great interpretation of Carlos Santana's "Smooth." (A song with one of the best lines I've ever heard: "My Spanish Harlem Mona Lisa.")
We should think about some of the jazz standards from earlier eras, by Ella Fitzgerald and the like. One thing that could be done is a double version of a song: for example, a straightforward vocal presentation of Begin the Beguine and then a swing version such as the one by (I think) the Artie Shaw band in Broadway Melody of 1940. This would take care of variety in rhythm.
As you watch Fred Astaire and Eleanor Powell dance to this, keep in mind what Sinatra said in his narration in the anthology film That's Entertainment: You can wait and you can hope, but you'll never see the likes of this again. But maybe a skater or two could add something to the legendary luster of this classic song.
http://www.youtube.com/watch?v=DWW6QeeVzDc