Legacy (dictionary meaning): anything handed down from the past, as from an ancestor or predecessor: the legacy of ancient Rome.
Legacy may be a lot more than this, but for a skater I think a legacy could mean how he/she contributed to the sport and left something behind for the next generation(s) of skaters.
With that definition, here is how I see the legacies of some skaters:
Midori Ito- Triple axel, 3-3 combinations, the power of her jumps and her personality on the ice
Elaine Zayak- multiple triples in a program, leading to the Zayak rule
Irina Slutskaya- her 3-3 combinations, but to me her legacy is bouncing back from a serious heart condition to win a world championship in 2005.
Michelle Kwan- 5 world titles and 9 US national championships; she will be known as one of the toughest competitors ever.
Sasha Cohen- She took the spins and the spiral sequence to whole another level. Many skaters today do the I-spin.
Denise Biellman- Need I say it?
Surya Bonaly- Back flip
Lucinda Ruh- Her spins
Katarina Witt- Carmen and her ability to play characters on the ice
Kristi Yamaguchi- Her consistent jumps, particularly 3LZ-3t combination
Tara Lipinski- Her 3loop-3loop and as the youngest skater ever to win the OGM
Yu na Kim- Her OGM- the first ever by a Korean, and her skating
Oksana Baiul- Her artistry, particularly in the early years (the Swan, Meditation, Ave Maria, etc.)
Shizuka Arakawa- Her OGM at age 24 gave hope to late bloomers
Joanie Rochette- Overcoming personal tragedy
Mao Asada- Three triple axels by a lady in the Olympics
Brian Boitano- 'Tano Lutz and a whole lot more (jump consistency even as a pro among them)
Brian Orser- Two triple axels in a long program
John Curry- His beautiful lines and posture
Kulik- Awesome jumps and his 1998 LP costume
Yagudin- Athleticism & Passion
Plushenko- Very consistent quad combinations
Elvis Stojko- The quad. His ability to land it consistently in competitions pushed other skaters to do it and more (like Yagudin & Plushenko)
Lambiel- Spins (many skaters today are imitating his spins, with less success)
Kurt Browning- His artistry, and his Casablanca program
Petrenko- He made the 3axel-3toe combination a must for men (before Elvis pushed them to do the quad)
Torville & Dean: One word- Bolero (and their creativity)
Klimova-Ponomarenko: Their technical perfection and passion on ice
Anissina-Peizerat: Lady lifting the man
Grishchuk- Platov: Incredible speed, and her twizzles
Pakhamova-Gorshkov: First OGM in ice dance
Mishkutenok-Dmitriev: Passion (particularly Artur) and using her flexibility to create beautiful artistry on ice
The Protopopovs- Their balletic grace changed pairs skating
Shen & Zhao (actually this one goes more to their coach Yao Ming): High throws and split triple twists. It impacted skaters from other countries to try to do the same.
Irina Rodnina- her 3 OGMs
Sonia Henie- her 3 OGMs, and also the way she impacted the skating costumes (she shortened the skirts)
Berezhnaya-Sikharulidze: Sadly, they will always be known in N.America as the pair involved in the judging controversy/scandal. B&S fans in the rest of the world though will remember their beautiful skating. I think on a positive note, their legacy is their Chaplin prograams. They will always be remembered for those, even in NA.