In order for a mouse sized human to have equivalent intelligence, the brain needs to be scaled down about 3000 times (going on weight). This doesn’t seem impossible when you are considering stuff published about the theoretical computational capacity of matter. But whether it is likely to occur, especially as a result of a natural evolutionary process is impossible to say at this point.
Ask again after the singularity 
Without getting into a debate about the mathematical meaning of “complexity”, no the Menger Sponge does not encode significantly more information than a cube the same size. If you imagine a cube made of a perfect crystal of atoms in a simple-cubic arrangement, then you could specify the location of each atom in the cube by three numbers, corresponding to it’s “row”, “column” and “height” in the lattice. If the presence of a atom is taken as “1” and a hole in the crystal as “0”, then the string for the solid cube is “all 1’s” (a mighty compressed algorithm), while the string for the Menger Sponge could be specified by a recursive algorithm based on the definition of a Menger Sponge that would be quite small compared to the full string of 1s and 0s of a “bitmap” of the Sponge.
. . .
Wait, how is it less bulky? A donut with a hole in it is just as bulky as a jelly donut of the same diameter. Bulk is not quite the same thing as displacement.
If your starting cube is 81 cm to a side and you are limited to a resolution of 1 cm, the cube can store more data than the Menger Sponge. This is because if you can use every one of the 160,000 1 cm cubes in the Menger Sponge, you can presumably also use every one of the 531,441 1 cm cubes in the cube.
If you insist on considering the 81 cm cube as a single unit, you’re doing nothing but argue that stone blocks are poor methods of storing complex data, in which case the proper response is “No shit, Sherlock”.