You don't understand basics yet. There was no problem at Costco. Printer machines can only print maybe 250 to 300 dpi resolution (pixels per inch). Designed that way because the eye cannot benefit from more. Your 16 megapixels for 3:2 printing must have been around 4898x3266 pixels (16 mp).

But printing 6x4 expects only at most about
(6 inches x 300 dpi) x (4 inches x 300 dpi) = 1800 x 1200 pixels. About 2 mp.

So Costco had no choice, your input was entirely inappropriate size for 4x6. Your 4898x3266 images would be proper to print about 20x12 inches (at 250 pixels per inch). But for 4x6, they were about 800+ dpi, which is entirely not feasible. No printer can reproduce pixels at 800 dpi. Greatly excessive for the real world.

Your 1920x1080 pixel HD video monitor can only show 1920x1080. So in exactly the same way, showing a huge image is simply resampled smaller (to fit on a 1920x1080 pixel screen), and so you see about the same thing there.

Costco surely expects users will upload huge camera-size images like this, and they simply resample them to be able to print them, doing the work you should have done first.

You should prepare your images aiming to print at 250 to 300 dpi. 300 dpi is a fine goal, but most printers can only do about 250 dpi. Here are some basics:
http://www.scantips.com/lights/pixels.html