Postgresql improve select performance/parallelism in huge table
Although I didn't reach an answer for the issue (due to time constraints), I think that the most useful tip to remark is:

Use EXPLAIN (ANALYZE, BUFFERS) ... on many queries (with different values) to try to understand what is happening. In my case, this put back CLUSTER as a possible optimization option.

What I would do if I had the time to try to optimize the table:


Change the indexed values for the smallest possible. In my case, that would mean changing the user_id from VARCHARto UUID.
Execute CLUSTER to reduce the number of pages fetched.