Certainly a good challenge, although less accessible than a "start from scratch" assignment, is to refactor some existing code that either doesn't use inheritance or doesn't use very much of it to make greater use of inheritance. The process of refactoring will expose a lot of the benefits and gotchas of oop, as it certainly has for me on my most recent project. It also pushed me to understand the concepts better than past projects have where I've created my own object oriented designs.
Challenge: Write a wrapper for your web site/service API of choice in your language of choice, that doesn't already exist (ex. a ZenDesk API wrapper written in C#). Release the wrapper as open source for others to use.
Skill Level: Beginner to Intermediate
Rationale: To learn how to extrapolate a 3rd party web service API into a meaningful set of objects/classes, making the reuse of that API easier in your chosen language.
A given task has very little to do with being "OOP", it's more in how you grade it.
I would look at the Refactoring book, chapter 3, and make sure none of the bad code smells exist in the solution. Or, more importantly, go over ones that do apply.
Most importantly, watch for the existence of setters and getters (indicating that you are operating on values from a class and not asking the class to operate on it's own values)--or using "extends" without applying the Liskov Substitution Principle, stuff like that.
Take a procedural-style written piece of code and try to transform it into OOP based solution. During the process, consult a book on refactoring and design patterns. A friend of mine was able to make a huge step forward in understanding object oriented concepts exactly this way. As with anything, this might not work for everyone.
Write a challenging program from scratch. Try to get some people (around five, that should be doable) to use it. Respond to their change requests.
Adapt your program's design. Start small, then watch it grow. Manage this growth. This is hard. You will also have to fix bugs and maintain the thing over time, which for me was a very valuable lesson.
"The intent of this book is to help the beginning designer by giving them a sequence of interesting and moderately complex exercises in OO design. This book can also help managers develop a level of comfort with the process of OO software development. The applications we will build are a step above trivial, and will require some careful thought and design. Further, because the applications are largely recreational in nature, they are interesting and engaging. This book allows the reader to explore the processes and artifacts of OO design before project deadlines make good design seem impossible."