Hmm, it's tough to say, I had a tough time debating this as well. I pretty much started off the hard way from Bryce/Poser to Maya a few years ago and stuck with it. it's pretty easy to understand after a few weeks, also there is many good books out for it. I personally love the program and can do practically anything with it.
I tried 3DSMax and Lightwave for a few weeks, they in my opinion are a lot easier to get into, have great help files and user support, and you can make just as impressive things, plus 3DSMax is better supported in the gaming industry (if you want to get into modding). But in a few cases, I would need to shell out extra $$$ for plugins and such if you want to do some advanced stuff. Where in Maya Unlimited you get pretty much everything in one app. I haven't had much experience with Cinema 4D, I have a friend who uses it a lot for websites and makes nice things, but the renderer isn't that impressive.
I suggest after you pick a program, stick to it and read many tutorials, they help bigtime.
I pity da foo, thug, o villian that trys takin' over da world, then comes home cryin' to his mamma!
-Mr. T