> but it makes the site seem less legitimate

I have yet to head that cookie prompts are a sign of legitimacy. What business has customers that would think that way?

Not customers. Owners.

Although if you've ever worked retail, you'll know that plenty of customers are idiots.

Whatever "Surely no one is that stupid!" assumptions you make will be proven wrong no matter what you do.