We study the spectral norm of large rectangular random Toeplitz and circulant matrices with independent entries. For Toeplitz matrices, we show that the scaled norm converges to the norm of a bilinear operator defined via the pointwise product of two scaled sine kernel operators. In the square case, this limit reduces to the squared $2\!\to\!4$ norm of the sine kernel operator, in agreement with the result of Sen and Virág (2013). For $p\times n$ circulant matrices, we show that their norm divided by $\sqrt{p\log n}$ converges in probability to 1. We further investigate the finite-sample performance of these asymptotic results via Monte Carlo experiments, which reveal both non-negligible bias and dispersion. For circulant matrices, a higher-order asymptotic analysis in the Gaussian case explains these effects, connects the fluctuations to shifted Gumbel distributions, and suggests a natural conjecture on the limiting law.