May from Guilty Gear, a cute little pirate girl who fights with an anchor as big as she is.
Platinum the Trinity from BlazBlue has this in spades. She wields bombs, hammers, frying pans, bats, and frickin' missiles! And then she can upgrade them into things like swords and even BIGGER hammers. Bonus cute points for the magical girl motif.
Presea Combatir from Tales Of Symphonia, who was originally a lumberjack and wields a massive axe. She is the cutest character, bar none. At one point she is able to drag a heavy wooden log single-handed, a feat which neither Genis nor Lloyd can do together. This leads to Lloyd declaring that "I've lost all confidence as a man". She's a rare case in which the shortest character in the party is also the resident Mighty Glacier.
In another cutscene, the frail-looking Colette lifts Regal with one hand after Zelos couldn't lift him. This leads Raine to call all men useless.
And before that, when the party first meets Zelos, she grabs him and throws him with one arm when he approaches her with lecherous intent. Granted, she had lost her soul and heart at that point and could not control herself, but wow.
Hermana Larmo of Tales Of Innocence is a fist fighter, although she focuses more on speed and multiple strikes than sheer damage like Presea. Far from emotionless, though - she apparently teaches other superpowered young children clandestinely in the sewers, and tends to draw out the last syllable of her sentences (and attack names) into a "yan". Also, she's the reincarnated form of the divine dragon Vritra, whose form she can take in her Awakening Hi-Ougi.
Karol Capel of Tales Of Vesperia is the youngest member of Brave Vesperia (A guild he leads) Goes into battle wielding a Battle Axe while still dressed in his little overalls. He gets his moment in the Blade Drifts of Zopheir when he single-handedly fights a boss until he's disarmed, then grabs a nearby weapon and performs a backflip-attack.
This is further emphasized in the coliseum (in the PS3 version, a "Merciless" rank is available in the coliseum for team battles - at the end you fight the party members you didn't bring in with you), where Karol is so damaging that he's one of the highest profile targets after Estelle, who is capable of some spectacular magic spells and can heal and raise the dead.
Hinako Shijo from The King Of Fighters makes a rather amusing sumo wrestler, especially given the fact that she weighs just over forty kilograms (88 pounds).
Team Psycho Soldier has had a few cute bruisers on its roster in the later games. 2001 saw Bao, cute little boy and powerful psychic (and, to many fans, The Scrappy). XI replaces him with Momoko, a cute little Genki Girl that can perform ridiculously long attack chains.
Apricot Sakuraba from Galaxy Angel II. She also has a very strong case of androphobia, so whenever a man touches her, she involuntarily screams and flings him into the air.
Marcy of Chrono Cross is a tiny little girl in a frilly pink dress... and probably the toughest one of General Viper's elite, which includes a man about as big and strong as an elephant. Most of her moves involve beating you three ways to yesterday with yarn. Among playable characters, Leah, who despite being a child has great strength and HP; she is, in fact, basically a kid version of Ayla from Chrono Trigger.
Prolific in World of Warcraft, thanks to Purely Aesthetic Gender and the lack of substantial stat differences between races. You're just as likely to be beaten senseless by a two-foot tall gnome girl with pink pigtails as you are by a nine-foot minotaur warrior with a weapon larger than you are. Sometimes more likely, since the Gnomes are harder to click on in a crowded battlefield where tab-targeting is impractical.
With the Cataclysm expansion, female Blood Elf Warriors and female Goblin Warriors could also count as this.
This trope is inverted for male Draenei Priests/Mages, male Orc Warlocks/Mages, and male Tauren Priests.
Even more so in City of Heroes, with not only Purely Aesthetic Gender but Purely Aesthetic Appearance, period. A cute teenage girl can have the exact same powers as a hulking brute or musclebound, grizzled warrior, hero or villain. In-game examples include Mynx, a deadly Cat Girl and Fusionette, a reckless and bubbly Glass Cannon.
This is made even more extreme by the fact that the size scale can be adjusted from 12 feet tall to a mere 3 feet in height. Tiny heroes able to floor giant men made of rock, or withstand constant barrages of machine gun fire are so popular that the game picked up a fan-term for them: Microheroes.
Exelica and Crueltear from Triggerheart Exelica. One main feature of the game is that they use their grappling hook howitzers to grab and throw enemies hundreds of times their size.
Mazzy Fentan of Baldur's Gate II is a halfling paladin in an edition that doesn't let halflings be paladins. Statistically she's a fighter with some extra spells, but the behavior is all there. Voiced by Jennifer Hale, she manages to be tiny and adorable yet classy and honorable at the same time. Oh, and more or less a living buzzsaw through the forces of evil.
Alena, the Rebellious Princess from Dragon Quest IV. While she's very limited in what weapons and armor she can use, Alena's physical strength and critical hit rate are so much higher than the other party members' that it doesn't really matter. Especially once you equip her with a female-exclusive weapon that lets her attack twice per round. She also largely makes up for her limited armor options by having the highest evade rate. Basically, her kung fu is stronger than yours.
While Relm Arrowny may not be a great physical fighter, many believe she is the most powerful pure mage in Final Fantasy VI. This in stark contrast to her grandfather, the Blue Mage, and half-Esper Terra means that game balance might be Fridge Logic retardant.
In Dissidia 012 Final Fantasy, Prishe is the Token Mini Moe, a young Bare-Fisted Monk with Frills of Justice and purple hair. Her punch combos, particularly One-Inch Punch and Howling Fist, are incredibly powerful, those two in particular can crush guards and deflecting attacks when charged up, and her ability to link two attacks together gives her impressive power. For example, her Dragon Kick to One Inch Punch link has a base power of 25-35 if both attacks are charged up, making it one of the most powerful combos in the game.
There are a lot of characters in Touhou who could qualify. However, the greatest example would be Suika Ibuki, being barely three feet tall and about as developed as a six-year old... and an Oni with enough muscular power to smash a mountain to pieces between drunken binges.
Another good example is Suwako Moriya, who is not only an EX-Boss, but has the most damaging melee combo of any other character in the fighting spinoff, Hisotensoku.
Cirno is also a prime example. She's treated as relatively weak in-setting, but that's only because Touhou is full of extremely broken characters. From a normal human's (or even a weak youkai's) viewpoint, however, she's perfectly capable of freezing her opponents, the building they are in, and a good chunk of the surroundings while monkeying around. She IS right when she calls herself the strongest Ice Fairy; for her race's standards, she is enormously powerful.
Laharl, Etna, Yukimaru, and just about half of the units of Disgaea. It's not difficult to create an attacking force consisting entirely of BFS-wielding lolitas if you feel the urge to.
In Okamiden, Chibiteresu is even moreadorable. Yes, it's a god as a puppy. You may commence the Squee.
She may not have super strength, but Emilia of Yggdra Union otherwise fits the trope perfectly. The younger sister of the Big Bad, she frequently appears at the worst possible times, outdone in this respect only by Aegina and Luciana, and is one of the most difficult recurring bosses in the series... and she's only 14. Granted, the game's art style makes everyone look about 10 years younger than they really are...
Most female weapon-users in the Fire Emblem series are Fragile Speedsters or Archer, but Sacred Stones gave us Amelia, who starts out as a fairly raw recruit but can eventually become a General, Great Knight, or Paladin—or, for maximum application of this trope, take the "Super-Recruit" path, thus doing massive damage (as super-recruits have high Critical Hit rates) with a lance larger than she is.
Jill from Path of Radiance and Radiant Dawn (or not) might also qualify, as she's a member of the mighty Dragon Knight class and, according to a support conversation in Path of Radiance, is about the same age as the Token Mini MoeWhite Magician Girl.
Meg from Radiant Dawn is yet another possible future General.
Nowi from Fire Emblem: Awakening can become one if she class changes into a Wyvern Rider, as she's easily the youngest looking character out of the entire cast, yet potentially just as capable of handling a huge battle axe or lance.
In addition, any of the female children that are born can become a General and/or Dragon Knight as long as either their mother or father had access to the class.
Saki from the Oneechanbara series. She's 16, and looks even younger. She is a fairly solid swordsman... and her alternate combat style is fighting bare-handed and/or using throws, in which case she shows the ability to tear zombies' arms off with her bare hands or suplex them so hard their heads fall off. Yeah.
In Shin Megami Tensei: Nocturne, if you keep Pixie with you during the whole game, you can eventually turn her into this through a sidequest.
This carries over to Digital Devil Saga, Persona 3, and Persona 4, with a small caveat - they're all used on you.
Speaking of Persona 4, Chie certainly qualifies. An Extremity Extremist that literally kicks her way out of battle, her follow-up attack allows her to turn an enemy, as well as minibosses and even bosses, into A Twinkle in the Sky. On the top of that, Chie gains the powerful physical attack God's Hand, which will bring endless amounts of pain to her adversaries.
This doesn't begin to describe the unmitigated cuteness that Chie represents. Especially at higher levels and with proper equipment, her agility can get very high, to the point where she's quite difficult to hit. The cute part? When she dodges, she goes "Noink!" It doesn't stop being adorable.
And before Chie, there was Persona 2's Lisa Silverman.
Wild Flower in Jade Empire is a nice little girl... except the fact that she's possessed by two demons who are battling for control of her.
MOMO of the Xenosaga series starts the series off as a Magical Girl, but in the second and third games, she becomes a massive bruiser who can deal the most damage out of the rest of the party barring a Game Breaker like Erde Kaiser. Not to mention her version of another party member's attack in Episode III is stronger. And the other party member is the local cyborg.
Cinnamon from Mega Man X Command Mission. And add that to wearing armor that looks like a nurse uniform, or, in her Super Mode, a maid's outfit.
Ryugu Rena in Gaiden GameHigurashi Daybreak. Her first weapon is her butcher knife and when she's using it she's an uncommon female example of the Jack of All Stats. Her second weapon is an axe which makes her slightly slower but more powerful, as a subdued form of a Mighty Glacier (rare for a girl). Her EX-Weapon is a Cloud-likeBFS that boosts her damage output through the roof and makes her so strong she's a Game Breaker. Subverted by the fact that she's on full-Yandere mode when wielding this weapon, making her significantly less cute than the other, non-Axe Crazy examples.
The nameable Yoshi partner in Paper Mario The Thousand Year Door, who in series tradition comes out scrapping for a fight (and speaking fluently) as soon as he hatches. He's able to serve as a Power-Up Mount for a plumber three times his size!
B(aby) B(onnie) Hood aka Bulleta from Darkstalkers is a little blond girl, wearing a Red Riding Hood outfit. She's actually a bounty hunter that hunts Darkstalkers (especially Werewolves) for money and instead of bread and wine for Grandma, her basket contains machine guns and bombs. Did we mention she's also a Psycho for Hire in the most literal sense imaginable?
To drive the point home, if you are a muscular man that can put The Governator to shame and defeat a whole army of marines, you stand a chance at surviving an encounter with a C-class Darkstalker. A and S-class Darkstalkers (the highest there are) are outright terrified of Bulleta.
Hsien-Ko/Lei-Lei fits this trope as well perfectly. A cute and apparently harmless Chinese zombie girl, she can hold a wholesome set of weapons of all kinds of sizes and shapes in her sleeves. Not to mention she has strength enough to throw a character bigger than her into air.
Annie from League of Legends. To clarify, Annie is an eight-year-old girl, with masterful pyrokinesis and failing that, a 12-foot-tall feral shadow bear bound to her will... God help you if she invites 'Tibbers' to play.
In Fable II your hero as a child doesn't nearly match the levels of the other cute bruisers on the list, but he or she still manages to take down a much larger, stronger bully who managed to take down a similarly aged teen (namely Rose, your sister) with a single surprising headbutt. And does it in five short strikes with a wooden sword or a similar number of shots from a spit-shooter.
Talim from Soul Calibur certainly counts. She's the smallest human character, and quite possibly the lightest character. Yet despite her diminutive size of four foot nine, she can easily take down the biggest and baddest of the roster.
Xiaoyu, Lili, and Asuka in Tekken They don't look that imposing at first glance (especially waif-like Xiaoyu), but they have no trouble tossing around the heaviest of foes. Launching a 15-foot-tall demon into the air and flinging around a practically-solid-steel-and-osmium android like a rag doll, anyone?
Actually, almost all of the witches from the Luminous Arc serie are this.
A large number of Pokémon are this. Azumarill stands out, however: an adorable, beach ball-esque rabbit. Whose physical power (thanks to its ability) rivals heavyweight behemoths like Groudon and Zekrom by mere points.
Whitney and her team from '"Pokémon Gold and Silver ''. If you manage to beat her Clefairy, her Miltank will trash you.
Iris is easily the Token Mini Moe of the Pokemon Black And White games and anime series. In Pokémon White, she challenges you with a full-fledged party of Dragon Pokémon. In Pokémon Black, she can teach your Dragon Pokémon the most powerful Dragon-type move.
And in Pokémon Black 2 and White 2, she's the champion.
From the game Star Ocean: Till the End of Time we have the character Peppita Rosetti, whom, if you take the time to train her a lot, can become stronger than characters like Cliff or Fayt.
Irene from Shining Force III. A tiny woman with girlish pigtails, big doe eyes and a fancy Chinese-style dress, who doesn't speak the local language well for extra vulnerability points. Her method of fighting, in a game where most humanoid characters carry big ol' swords, axes, lances and the like? One oversized boxing glove and her feet. Oh, and she's a monk.
Veronica of Fallout New Vegas is a cheerful, slightly snarky girl voiced by Felicia Day whose main ambition is owning a dress (and she will Squee if you give her the right kind). She is also quite capable, with the right tools, of punching the head off of something. And she bubbles with eagerness to do so.
Liara in the Mass Effect series is a sweet, innocent young archaeologist who, at least out of combat, looks like a pretty standard pretty blue alien woman in a labcoat. In combat, she will start glowing blue, breaking peoples' necks by gesturing at them, and summon small-scale black holes to mess with enemy positions.
Depending on whether or not we'll ever see her face, Tali may count as one, too. Though she starts out relatively weak with great tech skills, upgrade her armament to Shotguns and give her the Spectre shotgun and watch her mow through some geth like nothing. And then she takes a level in badass between the first game and the sequel(especially)...
Ellie, the protagonist of Monster Tale, is a little girl capable of sending monsters flying across the room and breaking stone... with a satchel.
Milliarde of Baten Kaitos Origins is the sheltered daughter of an Alfard nobleman. She's seventeen years old, wears a cute dress, and has butterfly wings. In battle, she dual wields giant spiked clubs and sounds a little too happy, as well as serving as the party's Mighty Glacier.
Cecille in Suikoden III. Cute as a button teen girl who's shorter than even Thomas (and Thomas is a shrimp, by his own admission). She also patrols Budehuc Castle all day in full plate armor, wielding a spear larger than she is and a buckler, and trains every morning by running two miles in said plate armor. Her exclusive War Horse rune is also one of the most damaging attacks in the game, although it has low accuracy.
This is honestly just about every playable character in Neptunia. Take pity in those who are foolish enough to underestimate them just because of their looks, especially Compa with that giant syringe.
While it doesn't apply for all of them, a most of the Heartless look too cute to be an army of bloodthirsty creatures.
