While working with the query block and FSE themes I thought I'd give a look at what other CMSs do... Particularly Drupal.
Drupal has a "views" module. It's far more advanced than what we're trying to achieve with the query block, but it does have some good ideas. Its UI is more developer-oriented, and is not WYSIWYG, but I'll post a screenshot of its options below:

Left Column:

• Title - We add that as a separate block above the query if we want to.
• Format - Has options for list, table, grid etc. This is something that we'll need to have... Semantically sometimes they will need to be lists with proper <ul><li> items. Tables can come later, but it's important we have them as lists. Not everything is supposed to be a <div> on the web, and most themes (non-FSE themes) print lists on brogrolls 'cause that's what makes sense semantically.
• Fields - We add those as separate blocks.
• Filter Criteria - There are already other tickets to experiment with filters.
• Sort Criteria - There are already other tickets to experiment with filters.

Middle Column:

• Page Settings - The one thing we're missing here is permissions. But I don't think it should be implemented in the query block anyway... If at some point permissions are added they should probably be in a group block wrapping the query and not in the query itself.
• Header - We add this as a separate block
• Footer - We add this as a separate block
• No Results Behavior - This is a great idea and something we'll need.
• Pager - We add this as a separate block
• Language - Not relevant at this stage, WP is not multilingual (yet).

Right Column:

• Advanced options - Not relevant at this stage.

cc @ntsekouras @mapk