Well Drondor, I have a 57 SK and a 31 paladin. I've been playing EQ off and on since may of '01.

Both classes are obviously tanks, can heal themselves, get a lot of useful and important utility spells, and are important to any group. But the differences become apparent when you look closely at how the two classes operate. I'll break it down as best I can.

Shadowknights:

a. Can heal themselves without having to target themselves then re-target the mob. In addition, later in levels, SK lifetap-line spells can do some serious healing.

b. Have a powerful Harm Touch ability - with time and the right AA's, this ability can get very deadly indeed.

c. Physically powerful races, like ogres and Trolls, can be shadowknights. This means your abilities will be much higher where it counts, even without gear. You also get a free slam ability (if you like the two handed weapons, this is vital), and ogres are unstunnable (with melee) from the front (and from the sides too, imo).

d. Can fear their target, and have a snare spells (very good ones, too). This means you can fear kite. Being able to fear kite is invaluable for being able to solo.

e. Are free to enter most evil cities, or with little or no faction work (except for Cabalis). There are also a lot of quests that will help you to gain faction for the good cities, too.

f. You got a lot of damage over time (DOT) spells that will sap the mob's hit points while you fight - this adds to your ability to kill a mob. You also get a strong poison-based nuke line, that works on nearly all types of mobs. In combat, shadowknights are practically necromancers, considering all the damage their spells do!

g. Two words - Feign Death. The ability to plop over and appear dead will save your life many times, and is invaluable for situations for when you're losing a fight.

h. You get a pet. Yes, he's weak, but not after "child of Bertoxxulous" (sp), when the pet is about the same level as you. Even before then, he's quite handy - load him up with a mage's pet toys, and he becomes a serious player.

Paladins:

a. Have great faction, can get into all good cities, and can go quests to get into most evil areas (Oggok and Cabalis will be a problem though...)

b. Graphics. Many people like the look of the noble "holy" warrior. (You almost never see female trolls or ogres, and even males are not really common)

c. Stun line of spells helps to reduce mob damage, and can save your life in some situations. They also get a root-line of spells.

d. The ability to heal other party members - this is probably the single biggest advantage a pally has over a sk. Your "lay on hands" ability is the opposite of the "harm touch" of the SK.

e. The ability to resurrect (rez) others. Eventually, the pally rez is nearly as good as the clerical one. And as far as I'm aware, it's possible to rez yourself. This will save you money (and experience points!) over time.

f. A lot of smaller races can be (and are) paladins. Helps for fitting into those tight dungeon spaces.

g. Some really great spells for nuking, calming, bashing, proc'ing (that a word?) and otherwise killing the undead. However, SK's are also really good at killing undead (SK undead nukes are up there with the best of 'em, but SK undead utility spells are lacking somewhat).

Long story short - SK's can fear kite, kill with the aid of a pet, and heal themsleves while keeping the mob targeted. Since a main focus of the paladin is to heal OTHERS, he is at his best in a group.

I hope you get an idea of which class is the best fit for you based off of this.