There's different kinds of skills.
Nidalee and Lee Sin require the most practice and learning just to get to the same moderate competence you would with other champions, simply because they have 7 skills, all of which should see use, which requires paying a lot of attention to a lot of things. I'd give the edge to Nidalee here, just because her skills have more variety to them (support in healing and attack speed boosts, support in constant trap laying, harass with spears, chasing/fleeing with hops, and of course actually attacking, including AoE swipes or single target bursts). Not that Lee Sin is simple, but his skills are mostly combat and/or movement oriented. Still, he's also got support skills and is complicated, and needs to enter melee almost always to do his thing, unlike Nidalee.
Some champs require watching the entire map and knowing what's going on everywhere at all times to play perfectly, which is pretty hard to achieve, but it's also a skill that transfers between all of them. This pretty much includes anyone with a map wide effect: Ashe, Ezreal, TF, Pantheon, Shen, Soraka, Karthus. Of course, this map-wide-awareness skill is mostly the same skill that anyone with teleport should be developing, so in some ways it's easier to acquire this skill, and partially mitigated by anyone playing on a full team in voice chat. Of these champs I'd probably say Shen is the toughest to master, between timing and aiming all his skills and doing energy management (which isn't as much of a thing on any of the others).
It's a pretty hard thing to judge overall, especially since everyone starts with different people and some things are just harder for some people than others. I couldn't say that Shaco or Eve or Anivia or anyone else is just a wrong choice.