If the bottleneck is reading the information from disk you might upgrade the SD card or use a USB drive instead, which may have better random access performance. You could also store the portage tree on another machine with faster storage and access it over the network. If the bottleneck is actually calculating the dependencies, you are probably out of luck for the immediate future.
For calculating dependencies I suspect the larger bottleneck is reading everything from disk, seeing as the machines seem fast enough you didn't complain too much about actually compiling. In either case you should try to revisit distcc and cross compiling as that is the only reliable way to speed everything up. You do not necessarily need to use distcc with a cross compiler (the configuration most likely to cause problems, though the wiki does address this).
