Consegui resolver, mas foi difícil descobrir.
Resolvi instalar o Linux novamente, mas usando o 18.04.04 (prefiro LTS). O wi-fi também não tinha sido reconhecido, então o problema parecia ser com o driver.
Porém, após fazer boot no Windows algumas vezes, em uma delas o wi-fi funcionou. Então, desconfiei que o problema tinha a ver com o Windows, como mencionado pelo @zekkerj
Fiz então uma busca sobre o Windows desligando o wi-fi (algo que não imaginei que o sistema fizesse) e descobri que isso pode sim acontecer.
A solução: no Windows, usei Device Manager -> Network Adapters -> your network adapter -> Properties -> Power Management. Desliguei a opção que permite o windows desligar o wi-fi para economizar energia. Agora entro no Linux e está tudo bem com o wi-fi.
Então, o problema é que o Windows é traiçoeiro! Como meu micro é novo, não desconfiei disso e fiquei investigando o problema na partição Linux, mas o problema era com o Windows.