When I think about difficulty when it comes to games I think mostly about balance. Balance is really hard to achieve in games because there are different types of players....its hard to find a game that will satisfy both a grinder and someone who would want to quickly pace through the story.
For me I really like when a game makes me utilize as many different characters, techniques, and items as possible. I hate going through a game and finding things I never had a use for. With this in mind I really liked FFX in that it made every character useful in some scenario. The only problem that with the presence of Aeons that were far superior to most enemies that really didn't always have to be a strategy. Of course Aeons could be one hit KOed in some situations but you could still pull off an overdrive which did substantial damage. I enjoyed the pacing of that game for the most part and found some bosses who were decent however this game suffers the flaw of all of the final fantasy games since 5...you can without too much difficulty become extremely overpowered before the final encounter.
Now FFX did a decent job with making extremly annoying minigames but when you consider that if you go into the final encounter with normal leveling, doing no sidequests and the boss is really nothing to brag about, it puts it in perspective when in just a few hours you can kill him in two hits if you grind and do a couple sidequests. I like the added challenge of optional bosses but IMO the last encounter should be the most difficult in the game. And even Nemesis is not really that much to brag about as has already been stated in this thread.
If the game lets you get powerful in this way, it should allow you a way to test that power, and it should be able to balance that power in a way that cannot be easily exploitable(i.e quick attack over and over, counter/mime or any other crazy materia combination, the holy war item)
With all that being said, one of the most difficult and rewarding games I remember playing was Final Fantasy Tactics. You could grind in the game, and it was helpful to do so but the game curved that a bit by making enemies in random encounters scale with your level, and you would eventually not have the equipment to scale with the level of your opponent, making battles more difficult. I only wish Orlandu wouldn't have been so OP.