Both tanks and healers are in pretty high demand for XP groups. But, at the same time, clever players can make XP groups work (and work well) without either. So you probably won't be logging on to be instantly spammed with group invites with either class.
Cleric will certainly be "easier" to level 1-60. They are pretty potent for soloing undead, even with no twinking, from 1-50ish. They are far and away the best healers in the game. They don't have the paladin XP penalty. They have caster perks like bind and gate, plus rez. Cleric is definitely in higher demand at higher levels and in Velious.
Paladins are unique snowflakes though. Not many people play them, and they ARE very good tanks who also can solo in a pinch.
My advice would be to rely on your experience with EQ to pick the class that you think you'd have more fun with and then work on filling up a friends list (or getting a guild) so that you have people you know to group with. No matter your class, you'll find times when you have trouble finding a group, and having a go-to group of people to join makes a big difference... or at least gives you some people to chat with while you solo or keep looking for a group
[You must be logged in to view images. Log in or Register.]