OK, I will start with a few suggestions. I think, that what you really need is to understand Mathematica evaluator. Once you get this understanding, programming in Mathematica will become vastly easier for you, and you will be ready for the advanced examples showing the power of rules. So, here are the steps I'd take:
Read the book of David Wagner, "Power programming with Mathematica, the kernel" (1996, Computing McGraw-Hill). This is the best book I know to explain the essence of Mathematica evaluation process, and it is full of nice examples. Although it is currently out of print, you can get a free, licensed PDF copy of the book here.
While Wagner explains many things about evaluation process, some more details can be found in the WRI Technical Report by David Withoff titled "Mathematica internals" (thanks @Faysal for reminding me about it). It is a short and very interesting read, and even though it was published in 1992, it is mostly accurate to these days (which speaks well of Mathematica design consistency).
Get and read as many books by Roman Maeder as you can :-). There are four I know of, and I would read them in this order:
If you thoroughly read these, you will get more than enough background. They are not an easy read, but easily the best and most elegant exposition of Mathematica from the rule-based perspective, with plenty of non-trivial examples. I think his books are still unmatched, even though published way back. You should have no problems reading them after Wagner's book.
After that, you can hunt for rule-based code in many places. There are many nice examples in the books of Michael Trott, and also "Mastering Mathematica" by John Gray, as was mentioned in comments. There are also lots of good and non-trivial rule-based code in the past MathGroup posts, StackOverflow discussions ([mathematica] tag) and here on Mathematica SE. I will try to collect links to some which I find representative and post them here in this answer.
But, to summarize: first, understand the evaluation sequence and evaluation control (Wagner's book is IMO the best source for that, and I will add some links to evaluation-related SO and SE threads here soon). After that, the rest will follow. With your Scheme background, it will be much easier, since the recursive part of Mathematica evaluator is similar to what you know from Lisp / Scheme, so you will have to only grok the rule-based part (which is very substantial, and makes Mathematica evaluator really different).