My first encounter with challenge bosses was on Final Fantasy 5, Omega and Shinryuu, and boy was I in for a surprise, my party was instantly decimated even before I could input a command. Anyway here's my experience with these two powerhouses.
I found Omega easier, simply because he was nearer a save point, so everytime I lose to him I still have the momentum from the previous battle.
Omega is very fast, he also absorbs holy element, rendering powerful weapons like Excalibur and Holy lance useless against him, his defence is so high that most weapons would do 0 damage to him, including the hp absorbing blood sword I kept on using. He is also protected by a wall which reflects spells casted on him. He is supposedly weak against lightning, but if you do bypass the spell wall and cast lightning on him he'll just absorb it! His primary moves include a powerful earthquake strong enough kill the entire party with one attack, and a strong heat beam, but his most devastating attack is surge beam which inflicts incredible damage and constantly and rapidly reduces hp like poison. He can also petrify, confuse and instantly remove a character from the party, but he rarely uses them.
To beat him I equipped the entire party with flame rings to absorb his heat beam, and cast float on them before the battle to make them immune to earthquake. I equipped the main character with the brave blade which has 150 attack and had him hold it with both hands, then I spammed Omega with x-fight, while the rest of the party constantly casted Cure3 and shell to weaken damage form his surge beam. He would sometimes remove the main character form battle, when that happens I have another character x-fight him with the Masamune, though it usually proves futile so I just fight him all over again by using either using the reset spell or resetting the game.
My battle against Shinryuu was a total mess, I don't even remember exactly how I beat him. His primary attack is tidal wave which, like Omega's earthquake, can kill the entire with one hit. His other attacks include a snowstorm, a heat beam like Omega's, a powerful lightning3 and various status inflicting attacks like "old" and "zombify". He also has a roulette which randomly kill a character instantly.
Since he has tidal wave I equipped everyone in the party with coral rings, since they were instrumental in my win against Leviathan who also uses tidal wave. Shinryuu is a dragon so he is weak against Dragon lances, which can be stolen from crystal dragons, but they were pretty hard to find and steal from while keeping the party alive, so I only got, if I remember correctly, just one dragon lance. So once again I spammed x-fight on him, I was pretty confident that the coral rings would keep the party alive, until he casted Lightning3 and killed everybody. So I tried again and defeated him on the 2nd try, with 2 casualties though, mostly because of his roulette
Later on I found out that Omega's lightning weakness can be utilised by using a lightning3 magic sword, he is also susceptible to "stop". On the other hand Shinryuu can be inflicted with "berserk" and "dark".
On a related note there are some challenge monsters which can be fought again and again in FF5. A few examples are, Prototype (mini omega! lol), Skull eater, Shield dragon, Exdeath soul, and Gil Turtle. Unlike challenge bosses their weakness are more obvious and easier to exploit.
While they can be a tough fight, these bosses and monsters has quenched my thirst for a challenge. I fell they have made me a better and more resourceful gamer. Ever since then I have always loved fighting challenge bosses and always looked for one in every RPG I play, including but not limited to the ones below;
FF7: the two primary challenge bosses here are Ruby and Emerald weapon. Ruby tends to spam Ultima, so we equipped Cloud with this armor (forgot name) which makes most spells miss. Cloud never got hit by Ruby's ultima. Emerald on the other hand has this nasty attack which inflicts 1111 damage for every materia equipped, so we just equipped Cloud with 2 materias, Knights of the round summon connected to an HP absorb.
FFX: the first challenge bosses in this game are omega and ultima weapons, but they are really nothing much to talk about in comparison to the new challenge bosses, the dark aeons and Penance. The dark aeons strong in all stats, but what we were worried about was their speed and evasion, so we got our fastest and most accurate characters, (Tidus, Wakka, Rikku) and completed their sphere grid... twice, to make them a match for the challenge bosses. We also got them their best weapons. All dark Aeons were though but it was dark bahamut which stood out among them.
Finally we got to fight penance. We buffed the party with cheer and made them attack using quick hit. It was long and tedious but the party was doing fine and penance was never able to attack with his arms. We finally damage him enough to fight the second form. Now the second form has this attack called immolation. It luckily only hits one character, but removes all their mp, but that wasn't our primary reason for concern. We notice that every time Penance would hit a character with immolation, the next time he or she gets hit by immolation again he or she dies instantly, We were scratching our heads at what causes this. First we thought that immolation instantly kill characters without any mp, but that wasn't it. We finally decided to check on the status of character hit by immolation. We found out that immolation also lowers a character's defence greatly, so next time we restored there defence, then we were able to defeat penance.
FFX-2: FFX-2 has an entire "challenge dungeon:, via infinito. It's full of strong monsters, and a boss every few levels. The bosses can be weakened by oversouling them by fighting similar monsters. When oversouled they sometime lose their nastiest attack.
Their is really cool looking challenge boss somewhere in the desert called Angra-Mainyu, when the party challenges him early on, he'll only swat them away eventually. He can be fought later on, and this time it's to the finish. We defeated him by reducing his mp to 0, making him unable to attack, but with his mp he has some pretty devastating attacks
The Al-bhed also made a robot which is made of parts you give them, it has a powerful rocket attack, but it's not much to worry about. But I suppose it's still supposed to be a challenge boss.
System: AMD Athlon XP 2200+, nForce 2 ultra 400, 512 MB PC-2700 RAM, 40+320 GB 7200 Hard Drive, Geforce 6200 256 MB AGP , 384Kbps wireless broadband