I'd recommend beginner swing lessons. You'll learn all the basic turns, the basics of leading, how to fit moves in to a basic step, how to time the dance to the music. Many places have an hour lesson followed by several hours of social dance for cheap.

Once you have these basic skills it's not too tough to learn new dances. Look up nightclub two step, that one works well with lots of types of music. I second blues dance lessons, though I don't really like blues. Learn basic jazz steps by looking up solo jazz routines and copying them.