When to choose Stochastic Hill Climbing over Steepest Hill Climbing?
The steepest hill climbing algorithms works well for convex optimization. However, real world problems are typically of the non-convex optimization type: there are multiple peaks. In such cases, when this algorithm starts at a random solution, the likelihood of it reaching one of the local peaks, instead of the global peak, is high. Improvements like Simulated Annealing ameliorate this issue by allowing the algorithm to move away from a local peak, and thereby increasing the likelihood that it will find the global peak.

Obviously, for a simple problem with only one peak, the steepest hill climbing is always better. It can also use early stopping if a global peak is found. In comparison, a simulated annealing algorithm would actually jump away from a global peak, return back and jump away again. This would repeat until its cooled down enough or a certain preset number of iterations have completed.

Real world problems deal with noisy and missing data. A stochastic hill climbing approach, while slower, is more robust to these issues, and the optimization routine has a higher likelihood of reaching the global peak in comparison to the steepest hill climbing algorithm.

Epilogue: This is a good question which raises a persistent question when designing a solution or choosing between various algorithms: the performance-computational cost trade-off. As you might have suspected, the answer is always: it depends on your algorithm's priorities. If it is part of some online learning system that is operating on a batch of data, then there is a strong time constraint, but weak performance constraint (next batches of data will correct for erroneous bias introduced by first batch of data). On the other hand, if it is an offline learning task with the entire available data in hand, then performance is the main constraint, and the stochastic approaches are advisable.