Actually dance to the tempo / beat of the music as they look as bit silly on slow records

Oh hell yeah, I second that one! Maybe have diferent styles of dancing, or just diferent moves, depending on tempo...

Increase / decrease the number of men over time, like a real dance floor

Another good idea...

How about if they actually walked on or off the screen? One or two here and there randomly, with a good chance of multiple walk-ons / walk-offs durring track changes? That way, when the music changes, so does the dance floor!

Hmmmm...