The best compilation of code-golfing problems I've seen is Anarchy Golf [1]. Pick almost any problem you want, implement it in rhoScript naively, and you'll get a much shorter solution. (Except those problems which use things not currently present, anything like, say, floating point numbers.)
If you look at some of the examples I have compared to the programs others have written, you'll get a brief sense. My eight-queens is 17 bytes, the shortest on Anarchy Golf [2] is 42. A solution to the 196 algorithm problem [3] in rhoScript takes 16 bytes compared to 24. But that's just cherrypicking problems I found interesting. I haven't yet done a real random sample to see how well it does.
Note, however, that the programs you write in rhoScript don't yet format the output to conform correctly, so they may require a few more bytes for that.
[1] http://golf.shinh.org/
[2] http://golf.shinh.org/p.rb?N+Queens
[3] http://golf.shinh.org/p.rb?196+algorithm