Hill Climbing Algorithm - Optimum Step Size
Usually it worked for me that if the search space was know then annealing rate (divide the size size with number of iteration)helped to decrease/increase the step size gradually to get to local max/min but the draw back is it might get stuck in local and might need some "momentum" to go on, another draw back it it might be very slow.however it doesn't seems like the case with your question that you bother about it.

Please refer-
https://courses.cs.washington.edu/courses/csep573/11wi/lectures/04-lsearch.pdf

This paper proposes self adaptive step size search-
https://link.springer.com/chapter/10.1007%2F3-540-34783-6_56