I agree with Izzy. Maya's architecture feels a lot more open than Max's. Because the entire program is basically one gigantic MEL interpreter, it's very easy to go in a modify how things work. There's probably more to it, but from an artist's standpoint, that's how it seems.

Kari also brings up a good point. Maya's node-based architecture is very complex at first, but with that complexity comes a great deal of flexibility and power. Fundamentally, Max and Maya work the same way (at the code level), but, from a non-programmer's point of view, you get more access to what's under the hood in Maya's UI. in particular, I'm thinking of HyperGraph and HyperShade. Having the ability to modify the flow of connections within a graph or network is essential to getting the exact results that you desire. It is much more flexible and powerful than simply piling on modifier after modifier.

However, beyond the underlying architecture of each program, I think the biggest difference between Max and Maya is the workflow and methodology of the UI (did I even use the right word? :p). Without going too much into the nitpicky details, I would say that Maya feels more fluid, which is a very personal and subjective point of view. Even though I haven't used Maya nearly as much as Max, I feel like, even though I can do the same things in both programs, I can stuff done a lot faster and smoother in Maya.

Naturally, Maya is far from perfect. One thing I like in Max better is the ability to easily customize the entire UI. For instance, in Max, I can make custom toolbars as easily as I can create shelf buttons in Maya. However, in Max, these toolbars can dock on any side of the window or they can be tabbed bars (basically a shelf) or they can be floating palettes. You can also mix and match icon and text buttons in a single toolbar. I would love that flexibility in Maya. There are probably a few more things I like better in Max, but I can't seem to think of them right now.

Anyway, bottom line is to use whatever works for you. Neither program is better or worse than the other. As has been said, what counts is how you use it.