Saudações.
Primeiramente seria bom estabelecer além do preço, também o uso que será feito e desempenho que espera do equipamento que virá adquirir.
Neste ponto é bom pensar em tamanho de tela, placa gráfica, chipset, processador, HD (tamanho, velocidade) ou SSD...
Isto posto, começe a procurar pelo que mais se aproxima das suas expectativas dentro do seu orçamento.
Quanto a compatibilidade, citando marcas, posso indicar os HP (são dois aqui em casa) que me satisfazem plenamente com Ubuntu. Além disso, a Dell mantém uma linha que sai com linux da fábrica e ainda dá a oportunidade de configurar a máquina ao seu gosto (e $$$).
Se mora em SP Capital, sugiro que visite a Sta. Ifigênia, existem lojas que trabalham com seriedade e bons preços e você leva o produto na hora, já configurado, testado e pronto para uso, além de poder comparar vários modelos ao vivo, pegando na mão. Para mim o melhor modo de comprar qualquer coisa.
Boa sorte.