if your studio is a max house and you want to change positions within the studio, go max script and later C#. Otherwise, Python is the way to go. Using python for max rigs which wander around your production pipeline doesn't seem to be a very clever idea.
python, 3dsmax has the mentioned Py3dsMax, and maya supports it native, and it is a good starter language, and can even be used for web development since most servers also have python.
I'd also recommend Python, there is Py3dsMax for Max, though I'm not sure how widely used it is. Check out The Programming/Scripting MASTER THREAD for some links to get you started.
Wow, thanks guys. I didn't expect there to be such a clear answer here. I certainly heard of Python, and knew Maya supported it now. I'm defiantly going to look into it, but please keep the suggestions coming.