Near-critical plasmas irradiated at ultra-high laser intensities ( I > 10 18W/cm 2) allow to improve the performances of laser-driven particle and radiation sources and to explore scenarios of great astrophysical interest. Near-critical plasmas with controlled properties can be obtained with nanostructured low-density materials. By means of 3D Particle-In-Cell simulations, we investigate how realistic nanostructures influence the interaction of an ultra-intense laser with a plasma having a near-critical average electron density. We find that the presence of a nanostructure strongly reduces the effect of pulse polarization and enhances the energy absorbed by the ion population, while generally leading to a significant decrease of the electron temperature with respect to a homogeneous near-critical plasma. We also observe an effect of the nanostructure morphology. These results are relevant both for a fundamental understanding and for the foreseen applications of laser-plasma interaction in the near-critical regime.