Melissandre the Red from A Song of Ice and Fire fits the personality aspect (and becomes something of a mentor to Jon Snow during A Dance With Dragons), but as part of a low-magic setting she's limited to soothsaying and summoning creepy shadows. Given that she's one of a handful of people to show outright supernatural abilities at all, however, that says something.
Skuld, the half-elven sorceress from the 13th century Saga of Hrolf Kraki, the title hero's treacherous half-sister and eventual architect of his downfall. In the Battle of Hleidragard, she summons a giant demon-boar and makes her fallen warriors come to life again, so they continue fighting as zombies.
Fiona of Amber. Her personality is a mix between elegant Proper Lady (when it suits her) and Femme Fatale (when it amuses her); and she has Pattern-based powers which could easily destroy a good chunk of the multiverse.
While she may not match most examples in height, she more then substitutes with pure might. With ladylike grace and magical fire, Shantotto is to what this trope aspires! Oh Hohohoho!
Lulu from Final Fantasy X, of the Ice Queen variety. Also somewhat gothy. She is the most composed of the party members, and figures as a bit of a mother or sister figure to the protagonist, Yuna. She's quiet, fashionable, and of course uses offensive magic.
Dragon Age: Origins has Morrigan, a shapeshifter who is well-spoken and cutting—and evil. In the Dragon Age toolset, she's also listed as one of the few characters with "High" intelligence, and her biography notes that she favors a look of wild elegance. She's the most evil member of the party, and NPCs often comment she's very beautiful. However, romancing her will reveal a sweeter side.
Jessica from Dragon Quest VIII. Although she's a little more fiery than this trope typically is, she has a rich upbringing, possesses a sharp tongue backed by a British accent, and generally has an overall bearing that's more lady than genki. Also her penchant for fanservice is an actual game mechanic.
Radiant Historia has Eruca, a reserved literal Rebellious Princess who packs some of the most powerful offensive magic in the game. Raynie is a partial example, having the grace in battle and offensive power of a Lady, but being slightly more rough around the edges than is typical for this trope.
Not yet playable, but Nine/Konoe A. Mercury from BlazBlue is a very much one. Although she subverts it by having quite the fiery temper for personality.
From City of Heroes the Lady Grey, supreme commander of Vanguard. Easily the most powerful wizard in the whole game, ever composed, ever graceful and one wicked Dark Defender
Many female anima/dark/light magic users from the Fire Emblem sagas:
Seisen no Keifu: Hilda (villainous example, handles Fire Magic due to being of the Fala bloodline), Ishtar (Hilda's daughter alias the "Goddess of Thunder" for having major Tordo blood and thus handling the VERY strong Mjolnir tome). Possibly Aida, too; her class is Magic Knight.
Thracia 776: Miranda (though she's more Hot-Blooded than the standard), Olwen (who uses Thunder Magic and swords),.
Fuuin no Tsurugi: Niime, Druid!Sophia (Dark Magic), Princess Guinevere when you unlock her (Anima Maigc). Maybe Cecilia and Valkyrie!Clarine. Sage!Lilina has the skills, but attitude-wise she's more of The Messiah. Bruhnya is an Anti Villainous version.
Rekka no Ken: Sonia and Ursula, both villainous examples. Arguably, Valkyrie!Priscilla and Sage!Nino are two on your side. In the Back Story, Saint Elimine was said to be one.
Sacred Stones: Lute, specially if a Sage. Also the promoted L'Arachel, though she's more... expressive than others. Selena follows it wholeheartedly.
Path of Radiance - Radiant Dawn: Sanaki, for some. Also a well-trained Ilyana.
Awakening: Tharja, a Cute and Psycho Dark Mage who enjoys practicing curses and is a Yandere towards the Avatar. She also happens to be a Ms. Fanservice.
Rose from Street Fighter is among the closest to this trope that you'll find in fighting games. She fights with her unique Soul Power, which gives her one of the most elegant fighting styles in the series and always fights with an air of elegance and grace.
In Awakening: Moonfell Wood, the Witch of the Woods is a dark-robed witch said to be fearsome and powerful and she held off Dreadmyre's attacks with her magic. She's also loyal to the human kingdom and swore to them to protect the sleeping Princess until the day came that Sophia would wake and save the realm.
Rose Lalonde, from Homestuck becomes this after upgrading her weapons with Eldritch Powers. Made even more obvious in her Alpha universe counterpart, who's an adult.
Erfworld's Wanda Firebaugh is this to a tee. Interestingly, because of how Erfworld operates, she started life seeing her physical form as a Lady of Black Magic, something she felt she had to live up to.