I just got finished with the 3 underworld bosses and here's my take on them & their dungeons
Ice Cave:Aside from the new enemy formation, it hasn't changed that much. It's still the easiest of the 3 unless you encounter the new group a lot while underleveled. Alichino falls very quickly if properly equipped and fire attacks are used. I can't comment on his healing because I killed him before he could. I was overleveled due to grabbing treasures in each dungeon first. Blizzard was odd though, it only did 2-5 damage to each character and I thought it did a lot more.
Feymarch:With the addition of shortcuts and angel wings it's worth fighting here. The battles theme here is high damage resulting in blind and mute getting a lot of mileage. I think the exp could be lowered a little on the warrior + fiend fights because the 2 warrior + 4 fiend fight gave around 9000exp which was a little much. Ciriatto 1 and his zombies are pretty easy as long as he doesn't cast Stop on each character(a high Wil Porom can keep the party healed with Cure 2 I think). Ciriatto 2 is still the hardest boss due to his unique abilities and he felt faster to me(Twins L30 & L33+ for Cecil, Edge, Rosa). I think people will always complain about Ciriatto because of how much damage he does however he fits the Feymarch's "theme"
Bahamut's Lagoon:Aside from the removal of the damage tiles along the treasure route, it hasn't changed. Draghinazzo is a little slower however like Alichino he's all about having the right tools for the job. His weakness is pretty exploitable(only Porom can't inflict dark damage) and he only has two things to worry about(Blink & Comet). Thankfully blink goes away after a few hits and Comet's damage isn't too bad.
Overall the battles are just about right but, Ciriatto 2 is still going to cause complaints. Part of the problem is that you only have 2 characters who can inflict holy damage(Edge w/ Ashura and Rosa w/ Holy) compared to the other two(Fire:Flame Sword, Fire 2, Fire Arrows)(Dark:Cecil's Darkswords, Kotetsu, Bio, Dark Arrows) I wasn't high enough for Bio but, I'm sure some people will level the twins to 33.