My Pally is level 28 and has pretty much soloed most of that. I can take on Yellow and Orange solo mobs and Green ++ groups with relatively little difficulty. It helps having a lay on hands for emergency situations and the damage ward is hugely useful. That said, sometimes the levelling was slow going, but then I guess that's more down to the whole soloing concept anyway.
If you go a Pally, make sure you have two weapons. One a nice big two handed beast for maximum damage outlay whilst soloing and the other a good shield (I use a stormshield at the moment) and a nice one handed weapon to increase your AC should you end up tanking in a group.
Oh and as everyone knows, you get a horse which is always nice :)
Cheers
Minky