I left my old answer below. For very small $s$ I think that the right answer is about $M=N^{1/s}$ (for non-negative entries.) My reasoning is that one can pick all but the last entry of $h$ freely and then the last entry is forced and uniformly distributed in $[0,N-1].$ So if we run over the $k=M^{s-1}$ ways to make those choices keeping the entries under $M$, we expect the smallest possibility for that last entry to be of order $\frac{N}{M^{s-1}}$.

Here is a small experiment with $N=1009$ and $s=3$. Ten times I picked 3 random elements and then looked for the minimal vector $h$ (using non-negative entries) I expected about $p^{1/3} \approx 10$ to be enough most of the time. It got a bit higher than that but nowhere near $\sqrt{N} \gt 31.$

[855, 752, 433], [8, 7, 7]

[872, 804, 715], [4, 0, 5]

[862, 647, 603], [7, 1, 9]

[764, 731, 897], [7, 14, 13]

[352, 811, 776], [12, 8, 7]

[285, 653, 876], [13, 11, 6]

[334, 502, 752], [7, 10, 9]

[840, 788, 333], [15, 2, 15]

[48, 476, 627], [6, 1, 2]

[526, 55, 580], [7, 6, 7]

Allowing $h$ to have entries in the range $(1-p)/2,(p-1)/2]$ should (and does in similar experiments) make the max about half as big.

**OLDER** If $h\in \mathbf{Z}^s$ then $h$ might be said to have length $s$. Obviously that is not what you mean, but what *do* you mean? The separation between the first and last non-zero entries? The sum of the squares of the entries?

For either of those there is a "short" solution when $s \gt 2\sqrt[4]{N}$. Then there are $\binom{s}{2} \ge 2\sqrt{N}+\sqrt[4]{N}$ sums $g_i+g_j$ all falling in an interval of length $2\sqrt{N}.$ Hence some two are equal and there is sure to be an appropriate vector $h$ with all entries $0$ except two $+1$ and two $-1$.

If I compute correctly, then, for $s = 2\sqrt[4]{N}$, there is about an $85\%$ chance that there is $i \ne j$ with $g_i=g_j$ which allows only two non-zero entries, each $\pm 1$. For larger $s$ this becomes highly likely.

The cases above have $h\cdot g=0$ in $\mathbf{Z}$

If $s \gt \log_2{N}$ then there will have to be (disjoint) subsets with equal sum $\mod N$ and hence some appropriate vector $h$ with all entries $-1,0,1$. Probably we can keep $s$ much smaller and have such a solution with high probability. With $s \gt (1+\epsilon)\log_2{N}$ and $g_i$ chosen from $[0,N-1]$ one could even be sure to have an equal sum in $\mathbf{Z}.$

**Later** Thanks for clarifying. My argument for magnitude $1$ when $s \gt \log_2{N}$ still applies.

I am note sure what happens if the vector $h$ needs entries from $\mathbf{N}.$ That seems more natural (npi) to me.

Perhaps you do want to just choose the $g_i$ from $[0,N-1]$, otherwise the choice of $I_i$ matters.

Perhaps you meant fixed $s$ although it seems likely to depend on $s$. for $s=1$ one has the uniform distribution in $[0,N-1]$ or $[0,\frac{N}{2}]$ (non-negative vs integer case).