Idk who you talked to at Costco, but if they have an actual optical department, they can definitely do Rx sunglasses (polarized even!). I don't remember exactly how much mine were, but it was reasonable, if not cheap. But my Rx is strong enough that my glasses are never actually cheap.
Maybe they didn't want to do lenses for a frame they weren't selling?
tl;dr Costco does do Rx sunglasses someone was lying to you.