What's a fair handicap?
Take away a single unstarred order token from your set. Which one depends on how much handicap you think is needed. A huge handicap would be to remove a march token. A big handicap is to remove a support token or a defense token. A significant handicap would be to remove a consolidate power or raid token.

If you find those handicaps too hard on you, you can also try playing without an order token for a few turns (say, 3-5 turns) and then getting them back. Or, maybe, play the first 3 turns without a march token, then 1 turn without each one of the remaining tokens, then with all of them. This will make the game much harder to you, but then you'll not need to feel bad about doing your best against your opponents.

Something I do when I'm teaching the game is, for the first 3 rounds, play my orders facing up and explain the strategy. This shows players some possibilities they did not understand they could do and open their minds to new tactics. You can't do that for too long though, specially in games with more than 4 players.