Maya: Great modeling. Interface decent. Texturing insanely difficult, especially when dealing with alpha and multi textures.
I wouldn't call it insanely difficult, then again I went to college to figure it out. It just gives you way more options for texturing then say 3D Studio Max and I think because of all the options they provide for you, it can be a bit complicated looking.
You can find a number of decent tutorials for Maya Mapping here: (Along with a pile of plugins and textures, models etc. for just about any 3D program out there)
http://www.creativecrash.com/
The thing about Maya's texturing is that you gotta focus on bits and chunks at a time.
3ds Max: Same as Maya.
I personally found 3D Studio Max more limited and complicated in modeling compared to Maya, and while it's texture tools are pretty decent and easy to use, I find them more limiting then Maya's. But it's been a few years since I played around 3D Studio Max.
I'd suggest Maya above all others, but the program is pretty pricy, about the same price as a small motorcycle depending on what version you get.
Many movies used Maya, in Paticular, Final Fantasy, which was done on an early version of Maya...... it's abilities are far greater now.
I'll admit, I started on 3D Studio Max and was hooked on it.... I had a hard time wanting to get into Maya, because at the time I never heard of it and looked complicated.... yet since I got into it, I never touched 3D Studio Max ever again.