Marnie, I had exactly the same experience years ago: At the lab I went to, the machine-made 4x6 prints were almost always better than the 8 x 12 enlargements that were presumably made with at least a small amount of human control! I quickly learned to supply one of their own machine-made 4x6s as a "proof" so that whoever was making the enlargement could get it right. Absolutely amazing, in my view, but they didn't seem to find anything remarkable about it.
I soon gave up on this lab, switched to slide film and eventually got a scanner and photo inkjet printer so I could leave the lab out of the equation as much as possible. Start by switching to a different (better) lab. Explain to your new lab why you've come to them. -- Mark Roberts Photography and writing www.robertstech.com

