Very cool. Which server, and faction? If you’re rolling Horde on Faerlina, I’ve recently rerolled, and would be happy to level with someone.
I put together a Classic WoW warrior tanking guide a while back that you may find useful. I’d love any feedback on it that you might have.
As for the build, you’ve got a lot of options, and while some people do choose to level specc’ing deep prot, most go with an Arms or Fury build, with Arms seemingly being more popular, or at least recommended on guides from WoWHead and Icyveins.
Personally, I really like Arms, thanks to Sweeping Strikes and Mortal Strike, which are a lot of fun while leveling, and in instances, and also for PVP.