Base them on the types & interfaces used in the rule's source file

I would warn against this because the types we use internally are often incorrect / simplified. I.e. instead of declaring a union like { x: string } | { y: string }, we'll declare an optional type like {x ?: string, y?: string} because it makes it easier to work with (it's impossible for us to do discriminated unions for the config types!).

Base them purely on the rule's meta.schema[0]

There is the json-schema-to-typescript package which makes this pretty easy to do! I've used it before and it works pretty well for most cases.

Example output I've generated: https://github.com/bradzacher/eslint-config-brad/blob/master/src/types/%40typescript-eslint/array-type.ts
There are some issues with the types it generates, however. I think we can fix most of these up by fixing the schemas.

Note that the package also supports auto-adding comments to the types - we just need to add a description field to the schema!

because it makes it easier to work with (it's impossible for us to do discriminated unions for the config types!).

Would narrowing with "x" in options be an option?

Would narrowing with "x" in options be an option?

Yeah it would - but you have to do that narrowing everywhere, otherwise you can't access the property 😢.

i.e. everywhere you must do if ('y' in x && x.y === 'foo') { ... }, when it's much easier to do something like if (x.y === 'foo') { ... }
playground

which is why it's generally easier to just declare it as a single type with all optional properties!

Ah, I see what you mean...