Let

 I(k) = { u ∈ ℤ : 0 < u < p/k },

and let

 S(k) = { x ∈ {1,… ,q–1} : g^x mod p ∈ I(k) }.

Because g generates the subgroup of order q, the map

 x ↦ g^x (mod p)

is a permutation of that subgroup, hence for a uniformly random exponent x the value g^x is uniformly distributed among the q non-zero subgroup elements.
Therefore

 |S(k)| = q · |I(k)|/p ≈ q/k . (1)

Probability of hitting the target interval

For any algorithm that, at each step, evaluates g^{x_i} for some exponent x_i that is independent of the earlier outcomes, the value g^{x_i} is still uniformly distributed in the subgroup. The probability that a single trial falls into I(k) is

 Pr[g^{x_i}∈I(k)] = |I(k)|/p ≈ 1/k.

After t independent trials the success probability is

 1 – (1 – 1/k)^t ≈ t/k (for t ≪ k).

Hence Θ(k) trials are necessary to obtain success with constant probability. Since one trial costs one multiplication (or one modular exponentiation when x_i is chosen adaptively), any such method needs

 Ω(k) group multiplications. (2)

Optimality in the black-box (generic) setting

Relation (2) is tight: the naive method “try x = 1,2,3,… until g^x < p/k” needs on average exactly k evaluations and therefore already meets the lower bound.
No generic algorithm that only uses the group operation can do asymptotically better, because every evaluation gives only one new uniformly random group element.

(Although the usual generic–group lower-bound proof hides the concrete numerical representation of the elements, in our task the only extra information we exploit is the numerical value of g^x, namely whether it is < p/k. That extra information does not diminish the Ω(k) lower bound: knowing the exact value of g^x does not change its being uniformly random.)

What about special structure of g ?

The lower bound can be beaten only when there is some algebraic relation between the representation of g and the interval I(k). For instance, if g = p – c with c ≪ p/√k, then g^2 = c^2 (mod p) is already < p/k and the solution x = 2 is immediate. Well-chosen DSA/Schnorr parameters deliberately avoid such coincidences: in a prime-order subgroup the generator is (practically) random, so p–g is of the same size as p itself, and no exploitable relation is known.

Concrete parameters

With the numbers mentioned in the question,

 p ≈ 2^1024 , q ≈ 2^160 , k = 2^64 ,

we have |S(k)| ≈ 2^96 solutions, but the probability to hit one in a single try is still only 2^{-64}. Consequently an expected 2^64 modular multiplications are necessary and also sufficient; this is far below √q ≈ 2^80 and there is no known way to reduce it substantially.

Hardness of the “interval version”

Being able to exhibit, significantly faster than k steps, an exponent that sends g into an arbitrary interval of width p/k would contradict the standard belief that discrete logarithms are hard: by repeatedly shifting an arbitrary element by known exponents one could isolate its logarithm. Hence that more general task is believed to be hard as well.

Conclusion

In a properly generated Schnorr/DSA prime-order subgroup there is no method asymptotically faster than the obvious “try exponents until one works”. Its expected running time Θ(k) modular multiplications is already optimal for k ≪ √q, and for the concrete DSA-like numbers (1024-bit p, 160-bit q, k = 2^64) it means about 2^64 modular multiplications.