Max and maya both do the same thing... just differnet ways of doing it so go with whatever feels comfortable. I'd say Max is probably a little more conventional than maya but like mtmckinely said - Maya is alot more intuitive to use than max.. if youre artistic you'll probably find maya to be alot more friendly and productive once you have it set up to your needs.
One thing definatly going for Max is the size of the communities and 3rd party support - you can literally buy a plugin for anything and theres no shortage of books/tutorials avaiable which is why Max is often most peoples first 3d app which then leads to trying out SI/XSI or Maya.
my personal opinion - go with Maya of course! if i had the chance to start right off with maya then I would have jumped at the chance rather than spending a year or so mucking around with max and its clumsey awkward interface

Another really cool thing about max is the teapot primative.. what better way is there to make your raytraced chrome spheres over a checker floor (:wow: ) look even cooler than a shiny reflective teapot?! damn genius idea