Hi,
For me, navigation in 3d space and workflow are the most important when choosing a 3d application since almost all packages nowadays have support for all the basic tools that allows you basically do anything.
I started out on max and the interface is easier for the beginner since it doesn't really force you to use hotkeys. But once you're seasoned, you'll find that the fractions of a second extra to move the mouse around has a substantial impact on the speed/fun of doing a project.
I love the alt + mouse navigation system and default hotkeys of maya but I love the orbit around selection of max...
I would suggest starting with maya since it'll be easier to transition to other applications.
"Whatever tomorrow brings I'll be there...with open arms, and open eyes" - Incubus