It truly is a very personal question. The easiest class I had to level with was a minstrel, the fastest but most boring was a necromancer. I can't play a cabalist or sorcerer to save my life, yet I know a number of people who are very successful with it.
Right now I have an pally, merc and wizard I'm leveling (three separate alts.) They're all very different but a lot of fun to play.
I also tried going to Hibernia and Midgard (on Gaheris, co-op server) but I just can't get into the classes, not even the new (and some say overpowered) Vampiir or Warlock.
I know people who can't play Albion classes, so that doesn't surprise me. Best bet, play around with all of them. I'd recommend starting on Gaheris (unless you know people and have a server selected). You can swap realms there, testing out a lot of different classes, all the realms, meet a lot of really nice people and try it all without worrying about RvR. Once you're confortable with a class / realm, pick a regular server and start killing the enemy!
Theo