SG> My solution takes under a minute on my machine; the majority is the
SG> building of the word hashes.  Some of the basic techniques are:
SG> * Store the words in the sorted form, rather than sorting them each
SG> time

This reminds me of an anagram problem we had quite a while ago...
David A. Black wrote a nice little C extension which will sort bytes
of a word:

http://icarus.shu.edu/dblack/strbsrt.html

you can find the various anagram talk at:
http://blade.nagaokaut.ac.jp/cgi-bin/vframe.rb?key=anagram&cginame=namazu.rb&dbname=ruby-talk&max=50&whence=0

Anyways, I replaced your:
$Lengths[w.length][w.split(//).sort.join] = w
with
$Lengths[w.length][w.sort_bytes] = w

and went from 45 seconds to 15 seconds!

Yeehaw,
-joe