Healers: Warriors generally don't kill healers very efficiently, basically have to whittle them down. Interrupt as many heals as possible, and save your interrupts for only heals. Have your stun ready for priest's inner focus, or a paladin's aura mastery.
Classes I find easy:
Warlocks: Very easy for a warrior to solo, just gotta be aware of where their port is so you can position yourself to charge them after they port (impossible on z-axis maps though). Should be dead meat easy enough.
Hunter: They have 4 things to get away from you: master's call x2, and deterrence x2. As soon as you know deterrence is down for good, throw them down and pop your 2 minute burst (PvP burst trinket + deadly calm) and finish them. Use your charge to keep up with them after disengage.
Death Knight: Except for blood, DKs' melee defensive abilities are garbage. Just go really hard on them until they pop IBF, then wait for IBF to go down then throwdown + big CD to finish them off.
Boomkin: Kind of like warlock, except they can't even port away.
Shadow priests: Pretty much dead meat after the first dispersion, just watch out for wings. Save a throwdown for it. If they disarm you before you bladestorm, drop a bladestorm on them for big damage.
Classes I find challenging:
Rogues: Pretty much a hardcounter to warriors (which is ironic, because the exact opposite was true in vanilla). Their ability to get out of combat and reset the fight as many times as they'd like in a duel means they can control the flow of the fight. Also, their high dodge makes them very hard to kill by a warrior. Recup will also negate a lot of your damage. It's entirely possible for a rogue to finish you off in a duel while at 100% health.
Ret paladins: They aren't really hard to fight, provided their CDs are not up. Your only chance is to bait them into popping everything, then going hard on them to force them to pop shield, thereby negating their damage (shield cuts their damage by half), and afterwards you should be able to get a kill on a ret with no CDs left.
Mages: Another hard counter to warriors, needless to say. Basically make sure you never throwdown before a blink. If you can make it so that the mage is forced to blink before you charge, then you'll gain the upper hand. A good thing is to heroic leap -> throwdown after a blink, proceeding to pop a big DPS CD on them. If you can last until the second block is down, you will likely win eventually. Also, big thing is to not sit on your !@# and do nothing while you're nova'ed... make sure you are using spell reflect.
Ferals: If they're dumb and fight you without running away, you should be able to win just because ferals take a lot more damage from physical DPS then a warrior does. However, most likely the feral will try to dot you up and then run away. They can't quite reset the fight as easily as rogues, so if you think they're trying to run and predator's swiftness is up, pop spell reflect and force it back on them.
Anything not mentioned here is something I am not familiar with, or is a warrior mirror.