As you know, leveling a Klingon is as fun as being dragged over sandpaper naked. A few tips on how to keep yourself from going crazy:
You can often level faster in groups - team up, it makes the rinse-repeat PvE content easier to manage - and based on the math the more ships in space combat will often lead to better XP when in groups of 2 or 3 (not so much for groups of 4 or 5).
The content of the new missions is good, but the XP - not so much. Deep Space Exploration missions are good, but some of the empire defense missions can be better XP - if you are grouped.
Keeping the PvP queues moving in Season 2 is going to suck - the changes are just dreadful. Don't queue unless you intend to PvP - because not accepting the queue hurts everyone. It is basically a griefer tool now - so your best bet is forming groups and entering the queue as a group instead of a PUG.
When i levelled on tribble, i was really eager to play the pve missions from BG to LG, so i did them all back-to-back-to-back. Still had to grind out at least 1 1/2 levels, though.
The 2 repeatable missions with the highest reward are Empire Defense Against Borg Invasion and Defend the Gamma Orionis Sector Block, so i stuck with those 2.
I quickly found that there was a far larger number of Feds grinding the Gamma Orionis mission than Klingons grinding the Empire Defense one (naturally), so much that you could clear the map of hostiles before the map reset. However, the more Gamma Orionis missions you did back-to-back, the longer the delay timer became when attempting to re-acquire the mission.
My levelling advice would be this- do one of the new PvE missions, then go grind the Gamma Orionis mission until it takes you more than 5 minutes to re-acquire the mission. Then, go back and do another PvE mission-rinse and repeat.
Coolest part bout the Gamma Orionis mission is there will be more than enough Feds there to level your toon for you-several times i simply went afk, (and yes i noticed others doing the same, even Feds) most other times i didnt have to try hard at all to complete the mission due to the number players participating in the map.