In too many games I've played that have had some kind of cover system (good or bad), it always seems so obvious. Like you'll see a bunch of boxes and pillars, etc when an impending shootout is due.

So I'm wondering how could such a system be implemented without giving it away?

I speak mainly on third-person shooters. Not sure if any other genres have them outside of Action (Hunted: The Demon's Forge)

I hope it's not a hopeless situation,

There are more than a few ways to address this. One is to place cover everywhere. If there are waist high barricades everywhere you go then the presence of waist high barricades won't be suspicious. Another is to have dynamic terrain. Falling pillars that turn into cover seem to be fairly popular. Sometimes it just rises from the floor randomly. Have an aircraft crash and take cover in the ruins. Alternately you can have the player attacked even when there is no obvious cover. Not a popular option if these are hard fights, but can break up expectations. Also you can be liberal about what can be used as cover. If you can take cover behind more than just the usual waist high box then it's easier for your level designers to create varied terrain that doesn't scream ambush.

It's been tried before - I don't know to what success - but try letting the player and enemies make cover. I think the F.E.A.R. series let players and enemies make cover by flipping stuff like tables over. I wasn't too fond of it though because these dynamic objects were rare. Most cover was actually static. I never actually had to think about searching for cover and using it.

SiCrane explained it well. If you need some actual examples just look at a lot of first person shooters. The older Rainbow Six games do it well and that is because anything that can stop a bullet is cover. It isn't all waist high items but almost anything environmental found in the level.

It's the focus on "sticky" cover as a core mechanic that causes it to become so obvious. Especially over an 8 hour long game. If you put less emphasis on cover as a mechanic then you would most likely have less zone repetition. In this case it would be less open spaces with waist high objects around.

Cover is just an object that stops you from being hit, I use cover all the time in Call of Duty and it doesn't have what I'd call a "cover mechanic" built into it. If you want cover to seem more organic and less like the ubiquitous chest-high walls of Gears of War, just give your players a few basic abilities that will allow them to position themselves carefully with regard to obstacles in the world. Some suggestions:

Slow Walking: The ability to inch along, controlling your line of sight around a corner or over a ledge by small increments, allows players to "slice the pie", which is an intuitive and fundamental maneuver in gunfights. In fact, it's often better to stand a short distance away from a corner and peep around than it is to mash yourself against it and lean out. An analog stick seems like the best way to control this, but the PC version of Splinter Cell did a neat job of using the mouse wheel to control your rate of movement.

Leaning: On that note, the ability to shift your head and weapon to one side allows players to gain visual and weapons coverage around a corner without exposing half of their body to do it. I usually struggle with these systems, since they clutter up my controls, but if there was a really convenient way to use head-tracking or some other natural-feeling method to get that effect, I'd be all for it.

Crouching/Laying Prone: Sometimes you just want to hit the dirt, and a basic move like kneeling or flattening out can really add a lot to your intelligent use of the environment. A belly flop can turn a simple curb into a fortress, and hunkering down behind the engine block of a car can protect you from a great deal of firepower.

Each of these simple features, if well-implemented could help your players use cover effectively without making it feel gimmicky. Another thing to consider is how useful cover is. Nobody will use it if it doesn't impart an advantage. If your weapons all tear through the environment, if grenades are thrown like candy, if simple concealment can keep people from shooting at you more easily, or if taking cover just means you're stuck in a hole until someone inevitably flanks you and shoots your face off, then people won't use it so much.

If you're bent on making a system of sticky cover, look at various real life buildings and see how you could turn everything into sticky cover, if suitable. Like Iron Chef Carnage mentioned, add different mechanics for cover and not just sticky cover. It also depends on what kind of game it is. If it's stealthy, sticky cover may not be the best option for every situation if at all. If it it's more action-packed, then sticky cover may work well. If it's a little bit of both, then you may want to make certain mechanics situational or let them free or don't use some at all.

But cover is always going to be somewhat fabricated--even in Hollywood films because not all buildings are good for cover, which may be a thought you'll want to consider. Perhaps certain rooms are not clearly not meant for cover and so finding the room with natural cover is part of your level design.

You decision can also depend on who you are trying to make cover for, NPC or the actual player.

One thing I haven't seen much in games is human or animal shields. For example, from the AI perspective, there could be different class of bad guys that take hits from different types of weapons. One class of enemy could be armoured to the teeth and able to shield more vulnerable bad guys. Or perhaps have a swarm of expendable creatures that shield the more important ones, etc.

Cover doesn't have to be solid objects either; you can create cover via a hail of projectiles. The trick is to make sure the NPC is smart enough to recognise the threat and not stupid enough to walk into it.

I'm now reminded of Borderlands. I would always deploy my turret for my friends so they could use it's shields as cover while it healed them.

Makes me think that AI opponents should have at least some of the capabilities that humans have.