In Firestore, how can you do a compound query involving a key in a map without creating an index for every key?

As far as I know Firestore should auto-generate those indexes. From the documentation page on arrays, lists, and sets:

Consider this alternative data structure, where each category is the key in a map and all values are true:

// Sample document in the 'posts' collection
{
    title: "My great post",
    categories: {
        "technology": true,
        "opinion": true,
        "cats": true
    }
}

Now it's easy to query for all blog posts within a single category:

// Find all documents in the 'posts' collection that are
// in the 'cats' category.
db.collection('posts')
    .where('categories.cats', '==', true)
    .get()
    .then(() => {
        // ...
    });
)

This technique relies on the fact that Cloud Firestore creates built-in indexes for all document fields, even fields in a nested map.

While the lefthand-side of your where condition may be variable, that doesn't change the fact that these indexes should auto-generated (as far as I can see).

This is doable by setting the value of each category to what you want to sort on. Firestore has a guide that covers this.

Post {
    title: ..
    ...
    categories: {
        cats: createdAt
        puppies: createdAt
    }   
}

let query = db.collection(`/posts`)
    .where(`categories.${categoryId}`, '>', 0)
    .orderBy(`categories.${categoryId}`)
    .startAfter(lastDate)
    .limit(5);

Now Firestore allows the array-contains operator.
If you want to filter documents which contain specific value, try this.

First, change Map field to Array field.

Post {
    title: ..
    ...
    categories: [
        cats,
        puppies
    ]
}

Second, use array-contains and orderBy for each different fields.

let query = db.collection(`/posts`)
    .where('categories', 'array-contains', 'cats')
    .orderBy('createdAt')
    .startAfter(lastDate)
    .limit(5);

You can check the official document about array-contains operator from here.