Salvage and Einherjar were pretty good in the challenge department... despite some bad drop rate in Salvage and some horrible mob selections (Dark Elementals mostly) in Einherjar.
Limbus was mostly pretty easy. Dynamis wasn't really hard - and I found the old way really boring (too long).
Pandemonium Warden @ 75 was a good challenge, but not an entirely realistic one.
As far as Abyssea goes, Rani and Raja (without brew) are pretty challenging. I like the Alfard fight... it's one of those fights that's either pretty easy (if you know what you're doing) or a total disaster (if you don't have a clue). Dragua was a good fight with four (MNK, NIN, WHM, BLM)...
What I don't think qualifies as a good challenge is when a NM just constantly afflicts you with (an) annoying status effect(s) and outputs ridiculous amounts of damage constantly and you can't do anything about it except have Cure V and VI spammed on you constantly. That's more annoying than it is "challenging". The best example I can think of this is Bukhis. He basically destroys your shadows every 3 seconds, takes your Max HP down, then hits you with powerful 3-4 hit weaponskills. And doesn't stop. Not as hard as Rani, but far more annoying. Also not a huge fan of the "absorbing damage during WS" phase of Glavoid... it's not the idea I'm against, but more how it starts immediately as the NM readies his TP move. Due to the inherit lag between client and server, there's a pretty good chance you're going to have an attack round go off before you manage to turn. And it's always a triple attack proc with two kicks tossed in on MNK. And they're all critical hits...
Also, the best challenge this game ever had (in terms of being realistic and balanced) were the Chains of Promathia missions before they nerfed them into nothingness because too many people complained they were too hard.
I miss the reports coming out with the missions... like for pre-nerf Ouryu... "six of our servers top JP are dead outside the entrance to Monarch Linn" ... only bad thing out of the hard CoP missions were the "broken" teleports in Promyvion (could spend hours trying to go up a floor) and the really crappy trapdoor portion of Pso'xja.
I haven't tried the Khimaria NMs or the Omega Weapon in Uleguerand yet... I hear they are pretty tough.