I'm surprised no one has said international foxtrot. That's often the hardest dance to learn, not so much in the sense of figures (because some are simple), but dancing it well can be extremely difficult. Leading lady's heel turns is one of the hardest things to lead, I think, and still gives me trouble after years of dancing. (OK, I don't practice tons either, but that doesn't take away from the fact that it's hard to do.) I'm not sure exactly what factors people are considering when picking a dance that's hardest to learn, but international foxtrot really ought to be up there -- it's very difficult to dance well even when you know what you're doing.
If I had to pick something else, I'd say hustle because the way everyone around here dances it is with a 3 beat pattern. The musician in me has serious problems trying to dance a 3 count pattern to 4 beat music, so I've never really been able to learn hustle because of that. Yeah, some stuff takes 6 counts instead of four, but that's not hard (not for me anyway) because you can still at least match up every 2 beats and you're always starting on either a 1 or a 3. With 3 count hustle though, if you start on 1, then next starts on 4, then 3, then 2, then back to 1. I know plenty of people dance it like that, but to me it just really doesn't fit the music and that makes it too hard for me to learn.
So my votes would be first for international foxtrot because it's so difficult to dance well and second for hustle because dancing 3 count patterns to music that's in 4 is just confusing.
P.S. -- mademoiselle, you don't get dizzy in Viennese waltz if you dance it properly.

While there is a lot of rotation, the main motion is actually linear, down line of dance. I agree it's not exactly a piece of cake, but I don't think it's quite as hard as people initially think it is. Oh, changing directions fairly often will also help because as you sort of wind up in one direction, changing turns will help you unwind again.
--
James Marshall
marshall@astro.umd.edu http://www.astro.umd.edu/~marshall