[Striiker]

First off, I would not worry about the XP penalty. If you really want to play a paladin, go play him! Why the huge rush to level up? There is so much cool content out there for you to enjoy on the path to 60. Yes, it's always nice to hit that next sweet level spot where you get new spell or abilities etc. but it feels so good because the the journey to get to that level. (going through a hell level sucks but it feels so great after you've done it.. and we all have to do the hell levels..)
I made the mistake on live of trying to burn through levels as quickly as I could and I missed out on a lot. I'm trying to do dungeons and avoid the mindless grind-fest of outdoor zones such as LOIO, Overthere and DL when possible.
SO, back onto the subject. I'd suggest going with the class and race you want to play most and focus on that. Make another character of class which you can play for soloing times (because sometimes you only have an hour to play or have a hard time finding / starting a group).
Don't worry so much about the numbers of any given class out there. Make what you want and learn to play it well. You'll be loved by groups! I have played with people who don't play their class well at all and have played with people who really know how to play their class. The differences are stunning. A well played bard, shaman, paladin, etc. is simply amazing to have in a group. I hope you choose well and have fun in the game!