Ok, quest.. I VERY highly recommend the Antique Plate quest. You can look it up on the wiki, during the course of the quest you will get xp, Plate leggings, Plate helm, Plate BP, Plate Gloves, Plate boots, and 2 Plate Bracers.
They all have decent AC (about what normal plate) + some stat/resist. This quest is dueable in your later teens.
Dont neglect your Main Quest ether.. I am almost on the last stage of the Main quest now, and I am realy surpised by the number of people I see that are higher level then me and dont have there Main quest even started. You can gain a lot of xp during the course of this quest (which will take many levels to complete).
The newport ring quest is also a excellent quest and gives you a nice ring (since early rings/earrings are a pain to find). Erudin also has a odd newbie ring quest.. it doesn't give you much for a ring. but its better then a open slot.
I also subjest looking intot he newport sewers for some easy to get Earrings (nothing special.. but again better then ntohing) and a range slot item.
As far as specializtion, the general view by most people is it doesn't realy matter since you can max them all out in the end. However I dont really care for this view.. as it implys that everyone will be 65 with Tons of AAs. This is not for everyone, so my subjection is to figured out what you would like your paladin to be good at first.
Blade/Strike was one I went with first as it helps basicly all your weapon skills (except for blunts) 250 spec basicly gives you 10% bonus more or less (some very). At 125 spec your looking at about 5%ish bonus. I person took the road of giving me that 5% bonus to a couple of areas.
Blade/Strike
Blunt/Avoidance
The last one I can't hink of off the top of my head.. but its your midigation specilization. I currently have 140 Spec in each of those areas.
As to early upgrades Shrouded island has a fairly easy mob to camp that drops the Silver Plate Bp and Leggings. (hes in his low 20s) Not to mention the amount of undead in shrouded realy lets paladin do some good Dps (cleasening blows are x3 dmg)
Hope this helps