Some of the stories are not bad, but like any FF if you watch all the cutscenes expect it to be a mini-movie. I'm still trucking through the MQ story somewhere between release and HS, but I have not even tried to rush it. Whether I watch the movies honestly depends on how bored I am on a given night/how much I've had to drink.
Level to 60 with the first class is a joke. I did MQ and side quests and I was 60 before I even hit any of the "level 50" stuff. Leveling other classes is mostly easy, but there are a few annoying little gaps you need to fill with leve's and or if you can queue quickly, dungeons.
Things do get a little bit tougher at the higher end(coming from a non-raider, pub player only) but generally speaking it's still "avoid AE" level basic. There are some pretty hard gear checks though, for instance when i first hit 50 I did a normal group dungeon, wanderers palace or some shit. Well the tank pulled half the dungeon(first time I saw that) and of course I let him die as the healer. Grouped yelled at me to heal, like I was sitting there picking my ass or something, and tried again, died round 2. I'm normally decent or good at MMOs so I was getting frustrated too as I'm sure they were. Well I went back and did it again after getting a full poetic gear set and it's a joke. Little did I know that I my heals were healing for a MAX of like 400 the first time and now my average is like 1100....so there was just no way on earth I could have healed the multi-pull style run people do at the top end. Now I can DPS too with a few heals tossed in.
But insane challenge? No, no more than any MMO. I think the joy of this games comes from the ability to swap/try classes and the FF story. I have not seen anything revolutionary with combat or boss fights.