Interfacial thermal resistance presents great challenges to the thermal management of modern electronics. In this work, we perform an analytical study to enhance the thermal boundary conductance (TBC) of nanostructured interfaces with square-shape pillar arrays, extendable to the characteristic lengths that can be fabricated in practice. As a representative system, we investigate a SiC substrate with the square-shape pillar array combined with epitaxial GaN as the nanostructured interface. By applying a first-order ray tracing method and molecular dynamics simulations to analyze phonon incidence and transmission at the nanostructured interface, we systematically study the impact of the characteristic dimensions of the pillar array on the TBC. Based on the multi-scale analysis we provide a general guideline to optimize the nanostructured interfaces to achieve higher TBC, demonstrating that the optimized TBC value of the nanostructured SiC/GaN interfaces can be 42% higher than that of the planar SiC/GaN interfaces without nanostructures. The model used and results obtained in this study will guide the further experimental realization of nanostructured interfaces for better thermal management in microelectronics.