Eu iria por notebooks com chipset Intel e placa de vídeo integrada (ou seja, a maioria).
Se comprar com placa da Nvidia provavelmente não fará proveito, visto que uma boa parte dos notebooks tem tecnologia Optimus (onboard Intel + Nvidia), e isso está longe de ser bem suportado no linux (existe solução, mas não é trivial... você teria que usar o Bumblebee, teria que configurar tudo...), você acaba usando só a placa onboard Intel mesmo. Notebooks sem a onboard da Intel, que só tem a placa da Nvidia, pode ser melhor opção se precisar de gráficos melhores (o bmota aqui do fórum tem um desses notebooks, de gamers), mas ai tem q instalar o driver proprietário.
Gráfico AMD não tenho noção, mas eu acho que cai na mesma questão de gráficos hibrido.
Preste atenção ao wifi, broadcom é meio problemático porque você tem que instalar o driver proprietário, e se você não tiver internet por cabo, fica difícil resolver... e tem umas placas específicas que são chatas de configurar. Tem notebook com wifi e bluetooth que usa a mesma placa, wifi funciona mas bluetooth não (peguei 2 notebooks Sony com esse problema).