If you are just now starting on AAs then you simply need ALL the dps and defensive AAs, as well as all spell casting and healing and utility AAs. Which ones you get first should depend on whether you group or solo, and what your role is in the groups you get, and your play style.
If you are the tank, or if you are not geared enough to tank but WANT to tank, then start with defensive. If your role is support, like minor dps and backup healing and emergency offtanking, then you might benefit more from the dps AA first. Unless you never use your paladin heals then I would also recommend squeezing in some of those healing AAs.
Tanking = Defensive attributes + Aggro. Anyone that can hold aggro and live.
1. Combat Agility
2. Combat Stability
3. Natural Durability
4. Physical Enhancement
5. Divine Stun (for agro)
Once again I would like to mention Paladin heals. Healing adds very nice agro. Paladin have several weapons out there that proc heals. With a lifetap aug and the right AA it's very noticeable.
DPS = anything that remotely helps, even 1 point of damage
1. Combat Fury
2. Spell Casting Fury
3. Weapon Affinity
4. Finishing Blow
5. Slay Undead
6. 2 Hand Bash
7. Double Riposte
8. Knights Advantage
9. Speed of the Knight
Spell casting fury + weapon affinity is a very nice dps boost. Get a weapon with a built in DD proc, add in an aug with another and watch the pretty colors when it starts proc'ing and crit'ing several times a fight.
The AAs I mentioned are just the introductory ones for each of those types. There are often more AA available to boost those mentioned, but you would need these prerequisites first probably.
Also, there are of course more AA out there than just dps and tankish. Seriously consider the 9th spell slot (Mnemonic Retention), and of course the Holy Steed, and extra buff slots (Mystical Attuning).