Is it normal for it to take up to a minute for an execution plan to be generated (even an estimated one) on simple queries?
To process a query of this form:

SELECT *
FROM Table1
WHERE IndexedIntField1 = 12345
    AND NonIndexedVarcharField IN ('Value1', 'Value2', 'Value3')


The basic choices are to scan the whole table or to seek on IndexedIntField1, and then perform lookups for each row to see if the other predicate obtains.  If there a lots of rows IndexedIntField1 = 12345 then the table scan will be much cheaper, and if there are very few then the index seek + bookmark lookup will be much cheaper.

If the statistics necessary to decide which plan to use don't exist or are out-of-date, then, by default, SQL Server will create or update the statistics before picking a query plan.


  The Query Optimizer creates statistics for single columns in query
  predicates when AUTO_CREATE_STATISTICS is on.


https://docs.microsoft.com/en-us/sql/relational-databases/statistics/statistics?view=sql-server-ver15#CreateStatistics

and


  AUTO_UPDATE_STATISTICS { ON | OFF } ON Specifies that Query Optimizer
  updates statistics when they're used by a query and when they might be
  out-of-date.


https://docs.microsoft.com/en-us/sql/t-sql/statements/alter-database-transact-sql-set-options?view=sql-server-ver15#auto_update_statistics

You can see the existing statistics and when they were updated like this:

select *, stats_date(s.object_id, s.stats_id) stats_date
from sys.stats s
where object_id = object_id('sales.salesorderdetail')