Hmm, i would start of with blender or something alike.....But you should know this, if you start with blender now then that will be the prog you get used too. And if you're used to blender then making the step to lets say 3dsmax is very difficult.
So i don't think you should choose a programm on its difficulty, but just start in the programm in which you want the work the rest of youre life!!
And about the tuts, here are some 3d sites.
3dslinks
highend3d
digitaltututors
simply...
simplymaya°paid, and you can go to simpymax and simplylightwave through it.
And ofcourse pixel2life as said above.
PS: And blender would maybe a good prog because it´s free!!
just as 3dstudiomax and there is a thread on biorust about freeware progs. maybe take a peek over there?