Block ciphers as secure as AES but immune against cache timing attacks? This is a question out of curiosity! I really don't know of any other block cipher that is as secure as AES that has a substitution permutation structure and can be used as an alternative to AES to protect implementations against cache timing attacks.

Searching Google, revealed other NIST finalists, but the best of them had a Feistel structure. There are also many others, but there is less confidence in them compared to to AES.

I am looking for a good block cipher that is similar in structure to AES with same level of security, and efficient to implement in software, for both small and large devices.
There are no efficient attacks against AES that I know of (not counting the related key attacks on AES-256). The minimum security offered for AES-128 is still around 126 bits, and that's with pretty inefficient attacks. Furthermore it is studied very well, so nobody is going to present a cipher that has seen so much cryptanalysis (other than its predecessor DES). So yeah, "as secure" is going to present a problem I guess.

If you look at a cipher that doesn't use a Feistel network you might want to have a look at Threefish. It is a tweakable block cipher with a larger block size, a large number of rounds and large key sizes. As it is part of Skein, a SHA-3 finalist, it did receive some cryptanalysis. The main attack against it is a key distinguishing attack, which is not practical for the full round version and is not applicable when Threefish is used solely as a cipher. Oh, yeah, and it doesn't use tables :)