Do you think that object oriented programming is really necessary for absolute beginners? There's always this problem of coming up with examples with OOP when being introduced to beginners, and you can end up with horrific "Cat inherits from Animal" examples. GUI programming might be the best place to introduce OO since it's a decent fit, however a lot of newbie GUI programming would just be using a library, not building object hierarchies yourself.
Even the MIT "intro to programming and computer science" class (which uses Python) doesn't touch OOP until lecture 14, after dynamic programming, divide and conquer, bit of runtime complexity, recursion and more...