Elenarie: You played with a Paladin, and you're still alive? Strange that you didn't get bored to death.
My playthrough consisted of just using Holy Fire and Holy Freeze and running around like a fly without a head.
It is not a surprise. Paladin is a fighter(if you will use caster see below) and you build your character around Holy Fire and Holy Freeze and running? What is your primary attack skill? These are only auras. And not the greatest ones. That is just the worst way of playing Paladin.
You can build a classic Sacrifice + Zeal + Fanaticism paladin. Very powerful, quickly leveling up. Just cut through the hordes of monsters. Zeal allows you attack multiple targets(max 5), increases your damage and attack rating(chance to hit). Sacrifice is good for one powerful target and it also gives damage to Zeal.
But Zeal in Left Click Attack and Fanaticism Aura to right side. Fanaticism is one of the best skills in the game. It increases your and your companions damage, your attack rating and attack speed.
http://classic.battle.net/diablo2exp/skills/paladin-offense.shtml#fanaticism Don't forget to give points to Holy Shield. It is a wonderful skill raising your defence and block rate. Put 20 points in that.
Put the points in Dex until achieving %75 block rate with your best shield. Look for it when your Holy Shield skill is active because it raises your block rate you will need to put much less dexterity points.
Give Strength enough for your gear.
Rest of the stats goes to Vitality. There is no need for Enengy stat.
And also Hire an Act 2 mercenary. You can select a one with Might auro for more damage for you and him. Or you can select a Holy Freeze one for slowing monsters. Give him good items and together you will conquer the world of Sanctuary.
http://classic.battle.net/diablo2exp/basics/hirelings.shtml You can make a Vengeance paladin for a change and putting out elemental damage(both fire, ice and lighting). Use with Conviction aura that lowers monstres resistance to elemental attacks.
Also you can make a Hammerdin for a massive damage caster. This build also don't need a lot of items. But killing with flying hammers is not my style i think.