Entropic uncertainty relations are analyzed for the case of N-dimensional Hilbert space and two orthogonal measurements performed in two generic bases, related by a Haar random unitary matrix U. We derive estimations for the average norms of truncations of U of a given size, which allow us to study state-independent lower bounds for the sum of two entropies describing the measurements outcomes. In particular, we show that the Maassen–Uffink bound asymptotically behaves as lnN−lnlnN−ln2, while the strong entropic majorization relation yields a nearly optimal bound, lnN−const. Analogous results are also obtained for a more general case of several orthogonal measurements performed in generic bases.