¿Cómo empiezo con Maya?

Es de las más extendidas pero no es un all-in-one, siempre se usan otros programas adicionales o plugins para hacer ciertas cosas. Pero está genial que te lances a la piscina con él. Yo ahora estoy de lleno estudiando Houdini, que es otro programa de 3D con una forma de trabajar totalmente distinta y permite hacer ciertas cosas que con Maya no se llega o sería muchísimo más complejo de llegar al mismo resultado. Pero al final, todos se acaban complementando.

Como consejo empezaría haciendo cosas super sencillas para entender conceptos, y organizar el aprendizaje en objetivos concretos como comentan.
Empezaría en este orden:
entender interfaz > modelado > shading > lighting > render settings > UVs > texturizado > animación básica > rigging básico > dinámicas

Pero todo ello sin perderte en detalles, y luego ya podrás afinar con otros conceptos y herramientas que veas que vayas necesitando. Al ataque con ello! :)

Usar un programa implica hasta cierto punto casarse con él. Una licencia de estudiante de Maya te va a durar 3 años, después habrá que comprar un programa sumamente caro, pero si es que te quisieras integrar a un flujo de trabajo que lo use, adelante.

Mi recomendación para no " arla" al principio es.

Ponte objetivos.

Me preocupa esto: "he leído Maya es de las opciones más completas" es algo muy general.

También completo es 3D Studio, Cinema 4D y Blender por ejemplo. Hay pocas cosas que no puedas hacer con alguno de ellos.

Si no tienes objetivos estarás dando palos de ciego. Y no me refiero a objetivos como "Hacer los efectos de la mejor película que nadie haya visto". Me refiero a cosas como.

Animar un logotipo, hacer introducción a videos de youtube, hacer animación de personajes sencillos, hacer visualización de productos, etc.

Maya es muy extenso y puedes hacer prácticamente cualquier cosa. Desde mi punto de vista, es buena opción hacer una inversión en un máster/curso extensivo en alguna escuela que veas.
Antes de ello, también pensar, si conoces algo del entorno del 3D, qué quieres aprender o a qué quieres dedicarte: ¿modelar, animar, hacer rigs, entornos, lighting, shading, videojuegos en general etc?

Por lo demás, hazte una cuenta en autodesk y te descargas el Maya 2017, o el que quieras, con una licencia de estudiante, y puedes ojear lo que te apetezca. Yo diría comienza primero con el modelling, con lo cual te familiarizas con el workspace de Maya, el GUI etc.