Gnome Paladin is where it's at.
To give you a more serious answer--you need to share a little bit more about what you are looking for in a healing class. Priests have two talent trees than can heal well, but are limited to one caster tree for DPS and faster leveling. Druids only have one healing tree (and it
is a tree), but can choose between tanking, melee DPS, and caster DPS for leveling and alternate roles. With either class, you can expect to wear a lot of cloth as you level (not too many caster leather pieces until later on), and you'll want to choose a DPS tree to level with rather than going for heals right away.
If you have access to heirloom gear and no clear idea of what you want, pick up a cloth chest and shoulders (and a staff if you can), and work on getting both classes up until you reach a point where you prefer one over the other.
Edited, Aug 9th 2009 5:32pm by isyris