Ich bin selbst Fan von Python, allerdings würde ich pers. "A byte of Python" als kleine Referenz verwenden. Es gibt eine dt. Version für Python 2 und eine englische für Python 3. An welche man sich hält, ist für den Anfang irrelevant; würde dennoch zu Python 3 raten, da es aktiv weiterentwickelt wird, auch wenn die Unterschiede zu Python 2 - gerade für kleinere Projekte - nicht besonders groß sind...
Auf keinen Fall das erwähnte OpenBook für Python benutzen! Es ist in Python-Kreisen ziemlich verhasst, weil die Autoren beim OOP-Kapitel vermutlich einfach nur aus anderen Sprachen für Python wiederverwendet haben, ohne auf deren Spracheigenschaften hinzuweisen.
Eine Website hat u.a. eben jene Kritikpunkte gesammelt.
Wobei ich gestehen muss, dass ich nicht unbedingt Python als Eingewöhnungssprache wählen würde, obwohl ich die Sprache gern mag. Das liegt an die vielen, eigenen Sprachmöglichkeiten, die die Sprache mitbringt und so in keinen anderen Sprachen zu finden ist. Fängt man mit Python an und muss sich später mit einer anderen Programmiersprache herumschlagen, kriegt man u.U. deutliche Probleme, weil Python einige Sprachkonstrukte anders behandelt (privat/public/protected-Variablen und Konstruktor/Destruktor werden in Python schon sehr anders behandelt als in den meisten anderen Sprachen... Von Quelltexteinrückung als Sprach- und Syntaxstil ganz zu schweigen... Triviale "Getter" und "Setter", auf die u.a. die Leute vom OpenBook unverständlicherweise total drauf abfahren, sind in Python ebenfalls so nicht vorhanden).
Mein Tipp wäre das bereits erwähnte C# zum Lernen, allerdings gibts 100%-Kompatibilität in den neuesten Versionen leider nur für Windows... C hat mit OOP leider kaum etwas zu tun, von daher würde ich ebenfalls gleich zu C++ tendieren - allerdings hast du mit beiden Sprachen das Problem, dass diese ungefähr in den 70ern entwickelt wurde und da Lesbarkeit und Einfachheit noch nicht sehr im Vordergrund standen...
Wenn du nicht ganz so schnell ins eiskalte C(++)-Wasser geworfen werden willst, aber trotzdem unter Linux programmieren willst, würde ich tatsächlich zu Python raten...