I leveled up to 44 as ret, because it’s a better leveling spec, and then went prot for a few levels to tank Uldaman and Zul Farrak a bunch of times (mostly to farm for Rockpounder and Big Bad Pauldrons). Then I went back to ret again to get to 60 and went prot again at 60 to do all the dungeons and gather decent enough gear.
When I went to prot at 40, I went all the way down to Holy Shield first. That helped with the final boss fight in Uldaman tremendously. Threat wasn’t so much of an issue in that fight as survivability was.
That being said, I would still recommend you get consecrate, then the rest down prot. Something like this:
https://classic.wowhead.com/talent-calc/paladin/050501-05305133
Then continue down prot as you level. Reckoning and 1h weapon spec aren’t really worth it for dungeon tanking and leveling (i’d rather put those points in imp HoJ, Guardian’s Favor, and Anticipation).
Your gear priorities when you are 40 and up should be Intellect and Stamina (basically ‘of the Eagle’ gear). Strength is nice for some gear, but it doesn’t help your overall threat that much, only your block amount, and only by a little. It’s not worth prioritizing strength gear just for a slight increase in your block amount. But it’s good to have strength gear for when you’re grinding and solo leveling.
But stamina and intellect are the 2 most important for tanking low dungeons. When you start hitting the 60 dungeons, you will then want to build spellpower and defense gear. The Deathbone set from Scholo is an excellent paladin tanking set. Remember, you don’t want to necessarily gear up like a warrior tank. Strength and agility don’t really help your threat generation. Only holy damage does that, hence having int so you don’t go OOM as fast. A tankdadin stacked with stamina and intellect is a good tankadin.
Ret is still the fastest leveling spec for paladins, because it scales with all the warrior gear that exists in the leveling world (most mail/plate quest rewards and profession stuff is warrior gear). Prot gives you some more survivability, but it’s just a slower leveling experience. SoR will still be your primary seal, and without a bunch of spellpower stacked, it doesnt do much. You will be relying principally on your white damage.
So if you go tankdadin while leveling, you will want most of your XP to be coming from tanking dungeons for people. I honestly love tanking dungeons as a paladin. It’s so much fun and gets even funner from the BRD and DM dungeons up. And tanks are generally the most in-demand class for 5-man dungeons, so you shouldn’t have a problem getting into groups or forming them fast.
EDIT: When you get to the bottom of Prot and get Holy Shield, start putting points in the ret tree for benediction and Improved Judgement are a must. Lower cooldown on judgement means you judge Righteousness more often, meaning your threat is much bigger. In the 60 dungeons your threat means everything when competing with trigger happy mages rogues and warriors.