Planning and Optimizing the table structure InnoDB MySql
Recommendation

"all the records belonging to one of the categories" --> Build a many:many mapping between records and categories.  To have that table optimal, follow the tips here .  Be sure to use a 2-byte SMALLINT UNSIGNED for the category_id.  (You should not trust that you won't go beyond 255.)

Then the query is something like

SELECT r.*
    FROM RecordsCategories AS rc
    JOIN Records AS r  USING(record_id)
    WHERE rc.category_id = 123;


This approach will do an index scan of a portion of rc to find the record_ids, then randomly reach into r via the PK.  Yes, there will be "hundreds of millions of rows" in rc, but it will scan only a small part of it, because all the entries for category_id=123 will be 'clustered' together (either in the data or the secondary index).

Critique of alternatives

If you have a column with a commalist of categories, then every row will need to be fetched.  That is a full table scan ("tens of millions of rows" = a few gigabytes) of Records.  (BTW, don't use LIKE %123%, use FIND_IN_SET() -- not faster, but less messy to handle edge cases.)

"a separate table for each category" -- This is a very common question on this (and other) forum.  The answer is "NEVER!".

"separate column for each of the categories" -- Gag me with a spoon!  The table will be fatter and, again, you will need a full table scan.

"200+ indexes" -- The hard limit is 64.  The practical limit is more like 5.

Building on Akina's and Acidon's comments:  With 8.0, you can use TINYBLOB or BINARY(..) and set bits.  This is about as clumsy as having multiple SETs.  Before 8.0, bitwise ORs (etc) were limited to 64 bits; now BLOBs work.  SET/BLOB/BINARY/BIGINT save the most space.  But your entire dataset is only tens of GB, so I don't see 'size' as a problem.  Even the many:many table I recommend will be only several extra GB.