I've been having a blast leveling up and doing missions and quests since 1.19 and I wanted to offer some of my thoughts and what I've tried that has worked, hasn't worked - and hopefully get other people to contribute or maybe help some folks out. Disclaimer: I've only done 34-38 since the patch as a THM, what I'm saying is purely based on that experience.
Company Leves have been absolutely amazing in Nanawa Mines (Rank 30) - I started them at 36 and was able to chain even level mobs for 450>575>650XP with GA up. The XP bonus from these mobs is MASSIVE - and the completion bonus towards the end is just icing on the cake. When I got to 37, I set the difficulty to make them level 39 mobs and have earned towards 700+ XP on a chain although they were much more difficult.
A few things about Company Leves for me personally: The "Kill as many as possible" is the real winner. I can get around 11 mobs when they are 2 levels above me - which totals about 9kXP in 15 minutes counting the final bonus. The "protect the dude" one - I cannot beat when they above me. There's too many "random aggro" mobs and mobs "on the way" that I just can't get to him.. once you DO make it to him and clear the initial mobs however, mobs come at like.. 1 per minute (at least on the easier leve setting) - but I failed this one several times when they were stronger then me.
So far in my gaming personally - this has been the best XP I have earned. It was great. I think the "Protect the Foreman" will be easier once I close in on 39 again.
Doing leves between Uldahand Girdania - I saw no difference in bonus rewards (which I was confirming for myself today) upon completion. I was typically able to kill stuff 2 levels above me - but the pace was much slower. The chain bonus is fairly significant however and I'm not sure if completion speed or chain bonus XP fairs better.
Behests.. oh my! I was able to join every Behest at Nophica back to back because nobody was doing them and it's a great bonus and quickly completed.
Questing.. believe it or not.. not too shabby. I got a bunch of 35 and 36 quests that were en-route to places I was going - and between mob XP and reward XP it was pretty nice!
Caravan Security... no, just no. Decent seals even if you do badly - but not a source of XP.
Unfortunately I have not partied yet - although I've seen shouts every time I was in town, so I cannot comment on the rate of XP from parties although I've heard it's quite good.
Anyway, I've been having a blast so far. Let's hear some stories!