O que você está experimentando é a diferença mais facilmente percebida entre imagens vetoriais e rasterizadas. Enquanto o primeiro descreve formas de maneira abstrata, o segundo trata de imagens como uma coleção de pontos retangulares, chamados pixels.
Você pode exportar as imagens com uma resolução maior, o que aumenta a qualidade em detrimento do tamanho do arquivo. Mas se você quiser manter a qualidade da saída, então você não deve usar JPEG ou PNG, mas sim um formato de arquivo capaz de representar gráficos vetoriais. Se é para impressão, então PDF é geralmente uma escolha que a maioria das empresas pode trabalhar. Além disso, é o formato nativo do Illustrator mesmo assim.
Nota: Você não quer realmente exportar gráficos vetoriais em um formato de arquivo como o JPEG, porque o JPEG é destinado principalmente para imagens fotográficas. Uma conseqüência direta é que o JPEG apresenta um desempenho extraordinariamente ruim com desenhos de linhas, bordas nítidas e alto contraste, o que não é incomum com gráficos vetoriais. O PNG é uma escolha muito melhor aqui, se você precisar de um formato raster e, geralmente, até comprime melhor essas imagens.