Really depends on what you want to do. Motion and AE are strictly compositors. AE is very powerful but a steep learning curve. Motion can be made to do many of the same things and is more user friendly. Maya is 3D and in my experience quite difficult to learn. I prefer Cinema 4D for 3D stuff.
[paolom]"it seems that AE is almost a requirement"
Yes, to a certain extent. It really depends on what you sell yourself as. If you are focused on motion design then you better be an AE guru. If you are an editor with the ability to jump into AE then that is a good skill to have. However, knowing how to use AE is not enough in my opinion, you need some desing principles behind it to be really effective with it.