Hariyama is vastly underrated, I'd make use of him.
Hariyama@Leftovers/Chesto Berry
Nature: Adamant/Careful/Impish
EV: some HP/Def/Sp Def/Att.
Trait: Thick Fat
Vital Throw/Cross Chop/Arm Thrust
Counter
Whirlwind/Knock Off/Fake Out/Return
Knock Off/Rest
Hariyama isn't gonna win any land speed records, so Vital Throw is an option. Enough things use Substitute in the Frontier to make Arm Thrust viable, and if you want pure attack power Cross Chop is there. With high HP and reasonable defences, Counter can help you with Flying types that would give you trouble, Hari can easily take a Dodrio Drill Peck unless it's CBed. Knock Off is very cool and should always be considered, and Rest is always useful for Countering. This setup fails a bit against Psychic types, so be wary of that.