Well, I can't comment on Shammy's now. Mine are stuck at 60 and 70. Also take my comments with a grain of salt as I don't go much past heroic 5s and the random LFRs. I mostly do guild stuff, farm old content, etc.
I think Paladin's are probably one of the easier healers to learn on right now. They are reactive healers mostly, like holy priests, but have absorbs which are just yummy right now. To really become good at a holy pally though, you've gotta learn how to be efficient at generating holy power. Once I figured that out, it got a lot smoother and easier. I think Paladins required the least amount of knowledge about the fights.
Holy Priests are very similar and just require you to be awake. They tried to add some complexity with the Chakra states, and I will admit at first they seemed daunting (especially at first when your state was based on which spell you first cast) but once you get used to it, it's fine. It does require you to know a little more about the fights so you can be in the right state or time the transition as necessary.
The one advantage about priests is you have two healing specs, which is just gravy as you can pick which you like. Personally, I like Discipline. I've always been a shield !@#$% even in vanilla (much to dismay of warriors at the time). It's always been my favorite spell as it's truly unique. Now, discipline does require a little more heads up on knowing when damage in coming. It has more CDs to use, but you sound like me at first and I always hesitated to use them. Now, I realize they are on 2-3 minute timers, so it's usually not an issue. I will even use them on trash if I'm being lazy so long as I know I have time before the boss for them to come back up. Spirit Shell was a little daunting at first until I learned how to time it better with incoming damage. It's incredibly useful though, and it's on a 1 minute timer so you'll use it a lot. I love to use it when I know I"m going to be unable to heal for a little while so I'll pre shield and do what I need to do (hymn of hope, etc).
If you are coming from a warlock, shadow priest will be a familiar transition. I got my pally to 90 and remembered I didn't like to melee much as DPS. Shadow OTH is wicked fun (pun intended).
So, my opinion, jaded as it is, is to try priest. The DPS spec is cool, Shadowform is the best visual ever, and you have two healing specs, which are very different and you can try both. And its rare when blizzard screws them both up concurrently.