Table with huge data takes long time to query
Your complaint here is rather inconsistent.  You talk about simple queries that just sort on updated_dt, but that is not the query you show.  Also, the query you did show did not take 15-30 minutes.  Is there another even simpler query that takes even longer?  If so, that would server as a better example.  Particularly if you turn on track_io_timing first.

The query you show orders by both updated_dt and id. While conceptually an index on just updated_dt could speed that up by requiring a sort on id only within ties on updated_dt, this is not implemented in any current version of PostgreSQL.  If you want an index to serve your multi-column ORDER BY, you must include both columns in the index.

If you want to make most things faster without building new indexes for all of them, you might want to get either an even larger instance, or provision faster storage.