If you go with paladin and you're a new player, go high elf or half elf with the TUNARE diety. don't kill anything in the plane of growth or any druids/treants ever.
Do this quest chain later on
http://wiki.project1999.com/Natures_Defender
It's almost as good as the paladin epic, and VERY easy to get one.
Don't listen to the people saying either class is gear dependent. They aren't, especially on the blue server. A 100 platinum weapon and a set of bronze armor will take you to level 50, and gear will start dropping after that. Both classes have near-zero loot competition later on, so you will get almost all the drops that you need easily, ESPECIALLY if you get into raiding. Paladins in my guild compete with 0-1 players for loot, my rogue competes with 20+ players.
If you go with a Shadow Knight, go with Troll or Iksar for the innate health regeneration bonus. You will thank me later. Trolls get access to classic/kunark plate armor, while Iksars have limited choices until the end game, but they also get an AC bonus to make up for the lack of gear. Going with a non-regen class is like gimping yourself, and the only way to increase your regeneration with items is VERY expensive. Plus it stacks with your racial regeneration, so even with the best gear in the game troll/iksar is gonna regen more health.