I have encountered a need for fast computation of a transformation $Ax$ where $A\in \mathbb{C}^{K\times N},\ K\sim 10^7,\ N\sim 10^3$ is designed, and $x\in \mathbb{C}^N$ has iid $\mathcal{CN}(0,1)$ components.

$A$'s design, in current strict analyses, demands $A$'s rows to be independent and identically distributed as $\mathcal{CN}(0,I_{N\times N})$. This demand can be relaxed considerably and I suspect the real requirement is weak closeness of the empirical distribution of $A$'s rows to the proper distribution.

What sorts of structures can be imposed on $A$ whose rows retain quantitative empirical similarity to a random Gaussian matrix while admitting fast multiplication?

An immediate candidate is Vandermonde matrices generated by a vector of norm-1 components but I cannot see in what sense it might be properly random.