It seems to me that algorithms like Blowfish and Twofish with key-dependent S-boxes are almost impossible to implement without table lookups, and thus are almost impossible to implement in software without being vulnerable to timing attacks (other than by linear search through a large array, which is much, much slower). Since these algorithms are also ill-suited to hardware implementation (since the S-box must be stored in RAM), this seems to make the algorithms suboptimal for all purposes.
Is this assessment correct? It seems strange to me that I can come to such a strong conclusion. Yet I cannot think of any way to (reasonably) implement key-dependent S-boxes in constant time, so my point seems to still stand.