Você pode:

• Diminuir o tamanho da fonte, até um tamanho mínimo que ainda seja facilmente legível. Se optar por isso, não diminua o tamanho para telas de todos tamanhos, apenas quando for necessário.
• Diminuir o espaçamento, até um tamanho que não fique poluído ou difícil de distinguir o que está sendo observado. Espaços vazios são importantes.
• Abreviar palavras do cabeçalho caso elas sejam maiores do que o conteúdo da coluna (e.g. Semáforo), contanto que a abreviação ainda faça sentido para o usuário. No pior dos casos, ele pode acostumar (Sem. = Semáforo), mas talvez você ganhe apenas 5 pixels com isso e então não valerá a pena.
• Deixar uma largura mínima para cada coluna, e usar um tamanho maior se o tamanho da tela permitir.
• Filtro de colunas visíveis: talvez nem todo usuário tenha interesse em todas as colunas sempre que visualizar a tela.
• Scroll horizontal na tabela para visualizar as colunas que não cabem na tela.

Todos os pontos acima tem seus prós e contras, mas se você tem uma tabela com muitas colunas, não conseguirá exibi-la num monitor pequeno de um jeito que continue legível.

Tem um artigo no Medium chamado Design better data tables com algumas dicas e GIFs mostrando o resultado de cada "dica".

Pra começo eu iria citar o exato link que já postaram anteriormente do Design better data tables, tabelas são complicadas de lidar, nesse momento mesmo to trabalhando num sistema 100% de tabelas como Product Designer -sim, sou product designer de berço, infelizmente, mas meu foco é focar apenas em Front-end logo menos-.

Pra começar o cliente parece ser irredundante sobre essa parte das tabelas, então trabalharei com essa premissa. Antes de definir algo, tu já se perguntou ou perguntou a ele qual o objetivo final do sistema no quesito device? Por exemplo, o sistema que citei anteriormente é 100% usado em computadores, ele não tem nem responsivo só pra tu ter uma ideia, isso é, não tem problema todas as colunas serem sempre exibidas. Porém, isso acarreta num probleminha chato que vou abordar logo abaixo.

Excesso de informações é um problema recorrente em quase todos os sistemas populadas unicamente por tabelas. Uma hora ou outra, num futuro próximo ou longínquo, vai rolar de ter uma tabela enorme, com colunas intermináveis, e isso pode acarretar num problema de leitura ferrado -acredite, o cliente vai lembrar o seu nome somente nessa hora-, sendo o chato da festa, vou pontuar pontos negativos em algumas coisas que nosso amigo Rafael (sou novo aqui no Tab, não sei se existe sistema de menção) pontuou.

• Diminuir o tamanho da fonte: Não te recomendo fazer isso, no quesito acessibilidade, tu vai atrapalhar o uso de muitos usuários com vista cansada, miopia e afins, mantenha um tamanho legível e não abra mão disso, essa parte de mínimo facilmente legível é muito relativa ao sistema, já vi apps com a interface toda bugada no celular de usuário pq ele simplesmente usava a fonte em 200%, pode ocorrer.
• Diminuir o espaçamento: Isso causa um problema que gosto de chamar informação claustrofóbica, é péssimo pra leitura, responsividade e flexibilidade de informações.
• Scroll horizontal: Cuidado pra não perder a linha de leitura, imagina comigo, são 20 colunas, eu chego da décima terceira e não lembro mais sobre qual informação estou lendo, vou ter que voltar a primeira novamente, isso é um incômodo grande no sistema. No link que citei anteriormente, tem uma opção bem interessante que é a cereja do bolo -quem come bolo com cereja?- e vou citar abaixo.

No seu caso a melhor opção é usar o Horizontal Scroll, mantendo fixa a informação pai da linha, não dando opção pro usuário se perder na leitura, sempre frisando a informação.