The most important thing in learning programming is to learn to think like a programmer, regardless on what language you use. Programming languages are in general (with a few exotic exceptions) all the same.
Regarding Python, Lua or e.g. Perl, personally I consider them about as good as Basic which few people consider learning nowadays. They're still used, there's a lot written in them and they provide some powerful tools but that's about it, they're pulled down by their aged concepts. Unless you need to use them right away I recommend starting with them later when you already know how to write a good program - otherwise the possibilities they offer will pull you the wrong way.
Personally I think Java is the best language for beginners.