Hey,
I first started with MAX, just playing with it a bit. It was quit easy to get a grip on the User Interface etc.
This schoolyear, my final year, I make an animation short with Alias|Wavefront's Maya.
I have to say: "wow, maya is fantastic"
On the other hand, it took me a lot more time to understand Maya (because it goes way further in many things than in max) but now that I'm getting a grip on it, I just can't let go.
If you should choose for Maya I would advice you to buy a good introduction book. I've read the books that come with the Maya package (Learning Maya, Modeling, Animation...).
Especially learning Maya is a great book; You get 5 projects that you have to deal with, from the beginning till the end. There's only one minor: they don't explain much why you do this or that. This I can understand, the book is now 530 pages, when they should explain everything then they'll have to publish a book of a couple of thousands of pages. There was a second problem with the book that I encountered: many menu items weren't on the right place in the book (I didn't read the Maya 4 book yet...)
But the book actually rox to get a basic understanding of Maya.
Other good tutorial things are: 'this site after getting the basics ofcourse' and especially video's. I promote video's over books because in many cases they are clearer and sometimes better to understand than books. (videos eg. Gnomon and Alias|Wavefront)
And I agree with the fact that for games, you'd better start with MAX.
Also for film you could go with MAX.
But these are actually the choises of big production houses... But you must know that when you search for a job that the knowledge of Maya is very liked (I just can't find the right word now 
) .
Also I would promote you to study the Classic Arts because they make your job as a computergraphics fellow a lot easier and also a lot more fun.
Hope you find the package you like the most. And the tutorials and the courage to go on.