EDIT: Here is my new central repository for all my videos
I've used max, maya and others and blender is my favourite.
Blender (like all 3D software) does take some time to learn but there are heaps of tutorials out there.
I have a few video tuts here http://www.rstralberg.com/blendertuts.html
And the whole list of all available are here
and here http://www.elysiun.com/forum/viewtopic.php?t=31669
BTW there is a native linux version of Maya 4.5 and I'm not sure about 6 that works well but is a bit outdated now.
Give Blender a go, it won't cost anything at least
as opposed to Max which is US$3500
Blender has the advantage that the community has driven its development. Give it a chance and it is well worth the time you spent.
If you want a newbie video tutorial, check out mine at http://www.rstralberg.com/blendertuts.html
- the "axe tutorial part 1"
Don;t forget to goto www.blender.org
and see what others are making with it too!