I'm currently working on a new algorithm which reminds me of the infinite monkey theorem (cf. http://en.wikipedia.org/wiki/Infinite_monkey_theorem).
The idea is to position different size brush strokes on an image to try and produce a kind of painting. The main idea is that the brush strokes are randomly (hence the monkeys...) positioned on the resulting image but are only kept if they produce a result closer to the original. Therefore if you run the filter long enough, with smaller and more precise brush strokes you should hopefully get a pleasing image. Well that's the theory anyway...
Here is an early example (just click on the picture to view full size), based on a photo of the city of Porto Venere (credits Stock.xchng):
The algorithm still needs a lot of tweaking, but I hope you'll like it.