Super Mario Galaxy had one in Bouldergeist. While seemingly easy he had attacks that blocked your paths, regenerating body parts, shot rocks at you constantly, and the only means to destroy it was to use stuff he threw at you that would explode if hit or held too long. If that wasn't enough, he also took twice as many hits as any other boss in the game besides the final one. His only saving grace is that occasionally he'd shoot golden rocks with coins at you (and that he's one of the most fun bosses in the game), but that did little to comfort players looking for one hundred percent completion who had to undertake a no damage run on him. When the Daredevil Comet comes into play, those golden rocks that he throws at you vanish, making him the hardest boss in the game.
Major Burrows also qualifies. He starts off easy, but once he Turns Red later on in the fight, he'll start charging at you with blinding speeds, requiring you to ground pound TWICE before he rams into you. Also, have fun chasing him down when the dirt trails he leaves behind get in your way.
Fiery Dino Piranha. Not only do you have to time your spin attacks perfectly when his tail is not on fire, but he's much faster than Dino Piranha, making it that much harder to catch up to him. Also, he pulls these 180-degree turns that can cause you to run right into him just as you're about to hit his tail. He only puts out his fire when he slows down, and if he sees you trying to sneak up on him, he'll reignite, pull a 180, and start chasing you again. When he has one hit left, he never slows down, although his fire still flickers on and off. In fact, "flicker" is the perfect word: at this point, you barely have any window to attack his tail. When his tail is on fire, it leaves a freaking fire trail behind. And not a straight line, oh no, the trail follows the... smashy ball thing on his tail, so it curves everywhere. And then, at 1 HP, he starts spitting fireballs all over the place.
Fiery Gobblegut from Super Mario Galaxy 2 is like Fiery Dino Piranha on steroids. He's annoying enough in his regular form (despite his glaringly obviousweak points), but his fire version takes it to the extreme. You can't touch his body without taking damage, making it very hard to take out his belly bulges during the short window you have open to you, and whenever he dive bombs the planet, he leaves lava pools. After the first three hits, he goes berserk, and it starts raining meteors. Thank God for the Cosmic Guide.
Also from Super Mario Galaxy 2, Squizzard. Fought in the middle of a sand whirlpool that constantly sucks you towards him unless you're standing on one of many tiny rock platforms. Throws giant rocks (and after you damage him once, spiky eggs) at you, which STAY THERE after they land until you destroy them. His weak point is his mouth, which he opens for half a second BEFORE throwing his last projectile (so by the time you've dodged it, he's closed his mouth again - you have to shoot at him and THEN dodge). You can only damage him using the (temporary) Fire Flower powerup, and you have to hit him five times (in quick succession, or he'll close his mouth and you'll have to start again) in order for one damage point to register on him. And when he's down to one damage point left, he gets these turret things on either side of him, that shoot spiky eggs at you EVEN WHILE HE'S STUNNED. And the eggs get in the way of your fireballs. But worst of all, he starts throwing massive bombs at you. And you have to do a perfect run on him if you want 100% Completion.
Both Bouldergeist and Fiery Dino Piranha return in the Bonus Dungeon of Galaxy 2, along with three other bosses. You have to fight the two with no checkpoints in between, but thankfully the checkpoint is before Bouldegeist. Then the Speedy Comet comes and you have to do all five bosses in five minutes. Bouldergeist and Fiery Dino Piranha... are Marathon Bosses depending on their AI.
Wendy Koopa. In Super Mario Bros. 3, the female Koopaling is the worst. While the others' attacks will fly offscreen, the rings of energy she fires will bounce round the room endlessly, as she continues to add more. If you can't stop her before there are more than three or so, you're not going to. Give Wendy a shot in New Super Mario Bros. Wii too. Essentially the exact same fight, but underwater.
Hookbill the Koopa from level 4-8 of Yoshi's Island. Easy like everything when you play it normally. But when you want the 100 Points, you're not allowed to take damage even once. And this boss has really bad attacks, heavy collision damage, and you have to wait 30 seconds when you get damaged! Prepare yourself to repeat this boss over and over again for 100% completion.
In Yoshi's Island DS, when trying to get a perfect 100, more than a few bosses are this way. Contenders are level 2-8's Big Bungee Piranha (tentacles and continuous rain of projectiles); level 3-4's Bessie Bass; level 5-4's Moltz, the Very Goonie; and, unsurprisingly, the three-stage final boss.
Super Mario Sunshine has Sirena Beach's Phantamanta, a giant manta ray that leaves behind electric goo and divides every time you hit him. Super Mario Wiki says there are 64 little mantas you have to vanquish. Even worse, when there are only a few left, they turn pink and actively chase you. Even worse, when going to refill FLUDD, you'll find some of the water pools are electrically charged.
To be accurate, the moment all mantas left are the tiny ones that you can actually kill, they will start chasing you. You can make the battle slightly easier by first dividing the manta into roughly four, then focus on dividing and killing one part at a time. You can also hide under the cabana roofs to prevent it from reaching you, since Phantamanta is actually a ghostly silhouette that floats on top of whatever terrain it encounters. Once the mantas hit huts or trees those parts of their silhouette will therefore appear on top of the object.
Cleaning Eely-Mouth's teeth is annoying, as you're underwater with HORRIBLE controls, and you have to be dead on when firing at his teeth to clean them. Also your life is slowly going down, and it's not obvious that you can use the bubbles to regain your health until it happens by fluke, and it takes a looong time to get low enough to hit him properly. Even if it is dead on, you have to be low enough for the water to hit his teeth to actually count.
Although most of the bosses of Super Paper Mario are relative pushovers (especially when compared to some other examples in the RPG predecessors of the series), Mimi can give people a major headache the second time you fight her in Sammer's Kingdom. She's even worse the third time you fight her. First, she crawls on the ceiling and spits out Rupees. You need to pick one up and hit her with it from below, then jump on her. Easy enough, right? Well, this process has to be repeated eight times. You have a very small frame of time in which you can jump on her, and if you don't do it in time, then she starts throwing the Rupees, which are much harder to dodge. Though you can hit her while she's doing this, it's a lot tougher to do, and defending will be your highest priority. Each gem does 4 damage per hit, which really adds up. Even if you're good at avoiding damage, it's a very time-consuming fight that will likely leave you wondering just when she's gonna die.
Super Mario Bros. 2 has Fryguy, the flaming entity fought in World 4. At first, it seems like you simply have to hit it with the mushrooms three times, and technically that's the idea. After that, however, it splits into four living fireballs that hop here and there, trying to hurt you. And the more fireballs you kill, the faster the remaining ones will move. Granted, it's possible to kill them all in one hit, but good luck with the timing. To make matters worse, the game had a glitch where if you touched the last fireball before it died, the door to the next world might not appear. (You could escape having to reset by using a code that killed you, but that just meant you had to try and beat this boss from the beginning.)
Want to fight the bosses of New Super Mario Bros. U without hitting them immediately after they get up? Iggy and Roy become a nightmare. Iggy will walk onto the ceiling and use magic to create Magmaarghs. After dodging them, you have to run next to the floor where Iggy is and wait for him to fall, then immediately attack. Then, Roy has a double sided Bullet Bill cannon and jumps between floating, moving platforms.
Ludwig in New Super Mario Bros. 2, especially in Coin Rush. For starters, the stage you fight him in (5-Castle) drains your time as you are forced to ride through most of it on slow moving fences; not even the super leaf can let you bypass these. He himself fights by jumping on chains and firing beams from them, and you have to hit him by launching yourself out of a cannon to knock him off. For the first and second phrases it's simple enough, but in the third phrase he swings around on the chain he's grabbing onto, requiring near-perfect timing to hit him. Also, time does not pause when you're entering and in the cannon, meaning that he is still moving just before you fire, so you can't rely on entering just as he swings over the cannon you're by. Again, put this in Coin Rush and by the time you start the battle you have to do all of this in only a minute, and that's if you downright burn through the level without collecting the coins.
Smiling Big Boo, the Boss of Chateau de la Terre, in Something is hard because of the limited throw blocks, contact damage from the Big Boo himself and the smasher covering a large portion of the boss arena.