I think your problem is your output settings. Given that a quality print is going to need 240 to 300 pixels per inch of paper, a 500 pixel long image is going to look good at only 2 inches long. A six inch long print really needs 1800 pixels.
What I would do in your case when exporting from LR is this. Create a VC and crop the image to match the ratio of your paper. You may have to select a custom ratio if your paper size is not in the existing list. On export set your colour space to sRGB. Tick the resize box and select the setting that allows you to specify both dimensions. In the measurement box set it ti Inches not pixels, and set the paper size in the two dimension boxes. Set the resolution to 300 PPI. This will ensure that LR exports the image at the optimum resolution for your print. I would also turn on output sharpening, select the paper type that matches your paper. I would use gloss for glossy and pearl/metallic papers and matt for everything else. I usually set it to high, but that is really something you need to test for yourself.
When you print turn off auto correction. I recommend doing your own cropping and resizing as on some machines if you have it do the cropping/resizing you then cannot turn off auto colour correction.