I think you could approach this along the lines of the way many software install or render programs run; particularly since you have no control over Server Load.
Your initial instincts to keep historical data to provide an
initial estimate seems like a reasonable approach to me as a
first display. However, until the first group of records is run, you don't have any kind of context to know what the
current server load is. Once the first group of records runs, then you can recalculate and give a more accurate estimate of the time for the job to run.
You may want to collect data that includes time for
first group of records to complete for a given type of batch job and
total time/total number of records (again for a given type of batch job). I think using this methodology would give you the ability to provide some
heuristics that account for server load. As an experiment, you may want to collect data to see if this changes or becomes a more accurate predictor if you also record time for
first 3 groups of records as well. Its all a matter of how complex you want to make your algorithm.
Whether or not the complexity of the query or the work the batch job does is significant, I can't say and that's why I've said
for a given type of batch job. That would allow you to group certain jobs you run that you feel are very similar into the same data groups should you choose to do so. If you initially keep all the data separate, you can later combine some of it should you find it similar in nature and "close enough" for your needs.