While not just a renamer utility, TotalCommander has so far beaten every other tool I've seen. When you combine its Find Files
feature with the Multi-Rename Tool
(which has support for regexes & templates), the ability to use content plugins (there are plugins for almost every format out there) and you can even send the filenames to your preferred text editor for further processing. It's shareware, though.
A crazy example: You could search for all .PDF files in your computer with sizes between 100K and 2MB, not older than 6 months, with more than 3 pages, and rename them something to [PublishedDate] Author - Title.pdf
(as read from the files' metadata), and send the filenames to Notepad++ for a final review and fixes, all in a matter of seconds.
And yes, it works also on folders.