While surfing around on the web, I came across the FreeRouting website. It lets you grab a Java app which does auto-routing. It takes time, but it is quite advanced.
One feature really caught my attention: the ability to take an EAGLE .brd file, auto-route (or just optimize) it, and then bring the results back into EAGLE. It’s all documented here.
Here’s what it did to the JeeNode v2 design (jee-pcb-003.brd), which was routed 100% by EAGLE (after quite a bit of tweaking to make it succeed).
Before:

After:

(there are some discrepancies between the two, due to some hidden ground planes)
I haven’t checked it much, nor applied any DRC’s, but if it’s all correct then that’s 9 via’s instead of 26 – not to mention the considerably simpler traces. Impressive!