If you want to learn maybe the "purest" implementation of object oriented programming, learn SmallTalk. Everything in SmallTalk is an object, and objects communicate exclusively by sending each other messages. Almost every other programming language has some non-OO "escape hatch," like direct access to data fields or primitive (non-object) data types.
Use Objective-C if you want to program the Mac or iPhone in the near future. It largely copies the SmallTalk model, but grafts it on to C, which means that you can still do all the non-OO things that C can do. This engineering compromise seems to have turned out to be a pretty good design choice, but perhaps not as aesthetically pleasing as the "pure" SmallTalk design.
I would also add that Smalltalk might be more frustrating to do "cool things". It's a gratifying language to learn as an experienced developer, but for somebody just starting out, the fascination comes from the end result, not the elegance of getting there.
I know when I was first starting out, I wasn't capable of writing an elegant line of code. I barely am now, but at least I can recognize it when I see it.
