Why aren't iterators in batch jobs lazy-loaded?

You're absolutely correct. The system basically gathers everything upfront. This allows the system to display the total number of batches before it starts processing the data.

The "why" has to do with general limits: you can't query more than 50,000,000 rows, so it needs to know if you'll break that limit and abort early, and there's a daily limit, so the system needs to know if you'll break that limit and abort early if your batch couldn't possibly finish before the limits are reached.

Here's how the process looks in pseudo-code:

Iterator<Object> iter = BatchInstance.start(context).iterator();
Object[] batchData = new Object[0];
Batch[] batches = new Batch[0];
while(iter.hasNext()) {
    Object value = iter.next();
    if(value != null) {
      batchData.add(value);
    }
    if(batchData.size() == batchSize) {
        batches.add(new Batch(batchData));
        batchData = new Object[0];
    }
}
if(!batchData.isEmpty()) {
    batches.add(new Batch(batchData));
}
while(!batches.isEmpty()) {
    BatchInstance.execute(context, batches.remove(0).data);
}
BatchInstance.finish(context);

The actual implementation is abstracted away from us, but it illustrates how the system implements the batching logic.

Instead, you'll want to build an iterator that can determine how many records there are, if your endpoint can provide a total number of records. For example, the Salesforce SOAP API includes a "size" attribute that tells the client how many records will be returned across all calls to the same QueryLocator via pagination.

You can then return a number of placeholders for each record, and then you'll want to call the pagination API and buffer the results in your Batchable class. You'll also probably need to use some state data using Database.Stateful so you can maintain your position across execute calls.

Alternatively, I've used designs where I just count to some reasonable value, then perform a single callout each execute method, process those records, and repeat; if I reach the end early, I can System.abortJob, and if I don't, I can chain to another batch call to keep going.

Here's a basic Iterator:

public class CounterIterator implements Iterator<Integer>, Iterable<Integer> {
    Integer max, current;
    public CounterIterator(Integer maxValue) {
        current = 0;
        max = maxValue;
    }
    public Iterator<Integer> iterator() {
        return this;
    }
    public Integer next() {
        return current++;
    }
    public Boolean hasNext() {
        return max > current;
    }
}

Your batchable's start method can simply be:

public Iterator<Integer> start(Database.BatchableContext context) {
    Integer expectedRecords = WebService.getResultTotal();
    return new CounterIterator(expectedRecords);
}

If you can't get a total upfront, then just pick an arbitrary value, like 10000 or so; you can always abort early.

Your execute method would be:

public void execute(Database.BatchableContext context, Integer[] values) {
    // Do your callout, then...
    if(noMoreRecords) {
        System.abortJob(context.getJobId());
    }
}

And you can finish up with:

public void finish(Database.BatchableContext context) {
    if(!noMoreRecords) {
        Database.executeBatch(new BatchableClass(), 100);
    }
}

Keep in mind that there are governor limits about daily usage.

With the introduction of chaining Queueable, and the ability to chain Queueable with callouts, we can daisy-chain multiple callouts efficiently without having to "guess" how many batches we need upfront from the Batchable interface. A simple implementation would look like:

 public class ChainedCallout implements Queueable, Database.AllowsCallouts {
   Integer pageNumber = 0;
   SObject[] records;
   Boolean hasMore = false;
   public void execute(Database.QueuableContext context) {
     getRecordsFromServer();
     persistData();
     if(hasMore) {
       System.enqueueJob(this);
     }
   }
   void getRecordsFromServer() {
     // do something to get records, set hasMore flag, update pageNumber
   }
   void persistData() {
     insert records; // Or some other logic
   }
 }