I haven't quite played all of the paralogues on Maddening (missing Weathervanes of Fodlan, War for the Weak, The Silver Maiden, and Retribution) but here are my thoughts of the ones I've done...(difficulty rating out of 5)
Death Toll: Difficulty 1 with a turn-1 boss kill, 4 if you try to rout. People say "warp-skip", but you start so dang close to the boss on the right that a Stride is good enough--I had Ashe Deadeye the boss and then Cyril Point-Blank Volley for the kill. The annoying thing about this map is that if you try to play it "legit", you end up having to Stride or Warp your way over to the bridge anyway, because if it's not down by Turn 2 the villagers will either get caught by the wolf or make a right turn and get blasted to death by magic. Also there are a lot of enemies near the starting point on the right side, which can make it difficult to find good positions for those units at first.
An Ocean View: Difficulty 1. You have a quite powerful flier, and it's a sand/coast map. The enemies just have no hope of reaching you fast enough to pose a threat before they're dead.
The Forgotten: Difficulty 1.5. This one seemed much harder until I realized that the thieves with droppable items never actually initiate combat--if their target exit is disabled because the stronghold enemy was defeated, they'll just stand in the corner and let you wail on them. Since you can ignore their attack ranges, you have more space in the bottom of the map to work with than you might initially think. The challenge is all in dividing your forces properly during preparations; once that's taken care of, the rest should flow naturally.
Eternal Guardian: Difficulty 2. Just be aware of where the Bolting users are and you should be good. I'd recommend clearing out the left side before you approach them, as they're on the right. The golems are oddly reluctant to initiate combat.
Rumored Nupitals: Difficulty 2.5. There are plenty of reinforcements to deal with, but most of them don't have high MOV and none of them are fliers, so they're unlikely to overwhelm you if you're careful.
Tales of the Red Canyon: Difficulty 3. I'm not exactly sure how this happened, but I had a way easier time with this on New Game with Golden Deer than I did on New Game + with Black Eagles. Part of it might be because on GD I focused on regrouping my forces with Byleth as soon as possible instead of taking on all the birds right away.
Land of the Golden Deer: Difficulty 3. The first couple turns can be hairy to survive due to your limited space available. After that, there tends to be a lull for a few turns before the rest of the enemies rush to the goal, which can be pretty difficult to deal with. For that reason, I tend to take advantage of the lull to push towards the boss and end him before the rush becomes a problem. This is probably one-turnable, though I never tried; in that case, it drops to a 1.
Oil and Water: Difficulty 3, with two special tricks. The first, pretty easy, is be sure you have a flier on your team (which you should anyway). The second is to make sure you recruit Hanneman, but not Manuela. On Maddening, unrecruited Manuela auto-levels to LV 21 for this battle. This gives her EXACTLY enough Spd to equip Nosferatu without being doubled by the Pegasi that eventually rush her down, and EXACTLY enough DEF to survive two hits total from them even if she misses with all of her Nosferatu counterattacks. This should buy you enough time to deal with them before they take her out, and then your flier can intercept the Rapier thief before he runs off.
Foreign Land and Sky: Difficulty 3...if you know to rout as much of the map as you can before triggering the reinforcements. That means taking care of the bottom-left, then moving everyone out of the bottom-left before moving anyone into the bottom-right.
Forgotten Hero: Difficulty 3.5. A weird one; for some reason, most Demonic Beasts are just not that threatening on Maddening mode even if they do take a while to bring down. The wolves don't move at first, and the poisonous beasts are slow enough to not be a big threat. The Snipers and magic-users, on the other hand, are much more troublesome due to them appearing out of the fog and hitting hard enough to pack a punch. Once they're gone, the boss is pretty tough on paper, but in practice Encloser or Banshee will make a joke of him, holding him in place until you're ready to take him down.
Sword and Shield of Seiros: Difficulty 4. It can be pretty tough trying to make progress against the constant wave of Pass reinforcements, but I discovered that if I sent a token force to approach the boats from the south (instead of just the north), it pulled a few of the enemies in the north down towards the south. That let me eventually move in far enough for the boss kill. Shamir can easily kill the wyvern reinforcements that enter the town, but if you don't have a way to intercept them over the water, it'll be a race against time. (It seems based on the dialogue that enemies entering the town a total of 5 times--even if they're not on consecutive turns and even if they die right away--disqualifies you from the best reward; can anyone confirm this?)
Darkness Beneath the Earth: Difficulty 4 if you want the reward. The mages can thankfully survive one round of combat with the monsters, and can be quite helpful when it comes to breaking them with their gambits, but once they do run out of gambits they tend to make normal attacks and die when it would be smarter to do nothing and live. It takes a lot of care to correctly determine how to split up your army and which monsters to go after first. I found Hubert's Banshee spell to be an invaluable tool for locking monsters in place, preventing them from attacking either my units or the green units. I never quite beat this without one of the dumb mages making a suicidal attack on the last Ally Phase, but I did well enough to get the special spear.
Legend of the Lake: Difficulty 4. Lategame fog is even more obnoxious to deal with than earlygame fog since the enemies have enough Mov to reach you from outside Torch range. Ugh. At least you can shut off the reinforcements? There's also a boss with pretty powerful magic and about 38 Crit, meaning you'd better have lots of Goddess Icons if you don't want every single combat with it to become a game of Russian Roulette. That said, as far as monster bosses with 500+ HP go, it could be worse...
Falling Short of Heaven: Difficulty 4 if you've played it before, 5 if this is your first time. You know what sounds like fun? S.T.R. Assassins and Pegasi. In fog! Actually, no, I don't think anyone in their right mind would call that "fun". Do yourself a favor and warp-skip to the bishop on the right so you don't have to deal with any Pegasi beyond the ones that are on the map to begin with.
True Chivalry: Difficulty 4 if you want the reward. As others have said, this one pretty much has to be a rush to the boss because of how many green units there are to save. In fact, if you don't take care of the enemies north of Rodrigue (by killing or gambiting them) he'll die Turn 1. The congested layout of the town, and this being a Part I paralogue, means you'll have to be basically perfect at using the movement options available to you (Stride, Dance, Warp, Draw Back, etc.) to reach and defeat the boss in time (Turn 2 or 3). Oh, let's not forget the boss is an Assassin on a fort, so you'd better hope the accuracy check RNG is in your favor. (Try using Assembly to pull the boss off the fort if you can.)
Insurmountable: Difficulty 4.5. Apparently Almyra has read the guides saying that Bow Knights and Wyvern Riders/Lords are the best classes, since that's pretty much their forces in a nutshell. After dealing with the initial onslaught, you'll find there's an endless wave of oncoming wyverns to deal with until you take out the wyverns with battalions. That makes for pretty slow going, but my Edelgard was pretty tanky so she was able to survive several rounds of combat with them and eventually make progress against the stream.
Dividing the World: Difficulty 5. Oh hey, it's the same map as the one above, and just about as hard, if not harder. Apparently heavy armor is useless since these ally knights cannot survive more than 1 or 2 rounds of combat with ordinary Cavaliers, which outnumber them 2 to 1. Pretty much all the enemies have high MOV. Your best bet is to pick one green unit and defend them with all you've got, since there's no way you're saving all of them in time. Thankfully, just saving one is enough for the relic.
The Sleeping Sand Legend: Difficulty 5. This is Legend of the Lake's boss, 38 Crit and all, but even stronger and with 15 more Attack Speed. That's bad enough, but to even get to him you have to slog through a desert of troublesome enemies that are almost all built to ignore the movement-slowing sand. After that, you'd better be careful about when you enter the central structure, as that triggers two pairs of Wyvern Lords to fly in from the west and north, obliterating anyone fragile who happens to be in their range. You'd better believe I let out a big sigh of relief when this one was done.
The Face Beneath: Difficulty 5. Hilariously, the Death Knight is the LEAST worrisome thing about this map. You need to somehow find some way to extricate Mercedes and Caspar from the cliff before the enemies eventually come after them, but if any of your units not named Mercedes or Caspar ends their turn north of a certain point, Mercedes and Caspar will be inevitably wrecked by NINE same-turn reinforcements. I basically lucked out on my winning attempt--Mercedes and Caspar were able to take down the beast in the northwest (Mercedes using a Resonant Lightning gambit and Caspar hitting it with two Fierce Iron Fists), and other than that they only got attacked by a magic user, which was one of the few enemies not strong enough to one-round either of them. It seems you need to advance north with your team just far enough to attract the attention of the enemies up there, but not move anyone beyond the stone pedestal in the center. This has my vote for toughest paralogue I've completed.
The Secret Merchant: Difficulty 3 on Crimson Flower, 6 on other routes. On Crimson Flower, this isn't anything special since you get to do it post-timeskip, but on other routes...this was the one and only paralogue where I just threw up my hands and said "Forget it". This is before the time skip, and you're expected to deal with S.T.R. Grapplers and Bow Knights (!!) that appear from seemingly arbitrary spots on the west, north, and east borders of the map. Yes, pre-timeskip, you're expected to handle enemies that can hit you if you're 12 spaces away from where they show up without any warning. I made two attempts at this, couldn't get halfway done, decided the rewards weren't worth the hassle, and moved on to the rest of the game.