As the previous commenter said, the Wolves or Worgs fit a Orc pretty well. However if you wanna go for something different from a wolf, try the tigers from Pandaria. They come in different colors and are bulky kinda like a Orc, in a way, matches pretty well.
Or if you wanna go full on Horde/Orc pride get one of the armored wolves from Hellfire Ramparts.
Anything native to Durotar/Barrens would probably work as well.
I find hyenas and cloud serpents to fit quite well if you don’t want the absolute bog-standard.
I agree a lot with this idea… but I also like the thought of a black wolf (or two), and then use Garn Nighthowl for your mount or go Frostwolves with a swift frostwolf mount