Not the most difficult to perform, but I’ve no doubt that the Knights of the Round Table number was brutal to shoot and edit. All those different angles, and guys dancing in armor – even fake armor can’t have been easy – and it all had to synch to the music. And after all that, Arthur and his knights didn’t even show up. 
Fred Astaire Dancing on the Ceiling. The room set was built to rotate along with the camera, but Fred’s perfect execution is what provided the magic to the scene.
Damn. What’s really incredible is that the vast majority of that is in one continuous scene- no cutaways. All of the really difficult stuff at least was done in one take.
They kept touring until they were very old (the younger only died a year or two ago). I wonder how long “they still had it”.
I love how he places the chair, and his jacket and hat, to cement the illusion.
From the movie All that Jazz the Air Erotica dance almways makes, ohhhhh, different kind of hard.
In the movie Oliver! there are a coupld of HUGE production numbers “Consider Yourself” and “Who will Buy”. The dancing isn’t that tough but I’ve watched these scenes carefully and when there is a cut to a new angle, part of the old shot is always there and it always matches. When this involves a few HUNDRED people, it’s pretty amazing.
Just a nit-pick, but the younger one died in 2000, at the age of 79. The elder died in 2006, at the age of 92.
There is this clip of Fred Astaire and Ginger Rogers, dancing while roller skating:
ShallWeDance?
The dancing starts at about 3:56.
I have always preferred Astaire to Kelly, but like them both. I can’t think of any other difficult dance sequences, really. There is a bit with Fred Astaire dancing in slowmotion while the background dancers keep real time, but that is more film stuff than technical dance difficulties (and I can’t remember the film it’s in-maybe Easter Parade?)
Also from Singing in the Rain - Moses Supposes with Donald O’Connor and Gene Kelly.
The chimney sweeps from Mary Poppins are pretty amazing.