My personal preference is for Python. I have done Java development in the past, but really do not like it - Java syntax is massively verbose which destroys readability, and it lacks features that I think are essential for any modern programming language such as first-class functions and closures. Without these features it can take a huge amount of code to do things that are trivial in a modern language.
Python is a good fit for linux development. It is pre-installed as others have said, and many Linux utilities are written in it.
You have a wide choice when it comes to GUI development - wxPython , PyGTK and PyQt are the main contenders, and there is also Tkinter which is a bit old fashioned but still usable. PyQt has the most restrictive license (free for non-commercial use, but you need to pay if you want to sell PyQt applications). The underlying Qt C++ code is LGPL however, and Nokia (owners of Qt) are working on their own open source Python bindings called Pyside.
wxPython has several GUI builders, such as wxGlade and Boa Constrictor. For PyQt you can use the excellent GUI builder that comes with Qt.