Nobody who doesn't covet a gun would consider carrying one around to not be an encumbrance. And we're not just talking about weight here. But it wouldn't surprise me that you, one who covets guns, wouldn't understand.
Is the source of the encumbrance the gun itself? Or the crime ridden area they live in where they may actually need a gun for self defense? I mean, really, I just don't get you. Are you honestly claiming that if we reduce the number of guns, crime will go down, and everyone will become more civil???
Well, with guns there is a sort of vicious circle going on in the US. As you said, its true that criminals DO have guns in Europe, and its not so difficult to buy one on the black market... But criminals (mostly drug dealers, "mafia" members, etc.) just do not carry guns around, they have them to kill other criminals or defend themselves from other criminals (or the police, if needed). In Europe, Spain, etc. you won't read about a random guy killed in his house (or on the street) because a robbery/assault, you will read about a drug dealer being executed by another drug dealer (just happened not so long ago near my house), russian gang members killing each other, etc... And still this happens just a few dozens times per year in countries with +50 million inhabitants, and nobody in my country feels unsafe or with the need to carry a gun.
Why? Well, as ALL citizens are unarmed, criminals are just less violent, especially with normal citizens. They do not fear for their life when they steal your call/break into your house (they know nobody will shoot at them... Not even the police!), so they really do not need to carry a gun, considering that committing a crime using a gun (even if you do not fire it) might get you tenfold the time of jail you would get if you commit the same crime unarmed. See, there is no need for criminals to use guns against unarmed citizens, from one side they are "safe" and there is no threat for their lifes, from the other side going around with a loaded gun is a huge crime in Europe which would get them A LOT of additional jail time, so its just plain stupid to carry guns.
So, there you have the vicious circle - you say criminals are violent, so you arm yourselves and prepare for the fight and criminals get more violent and prepare for the fight. Honestly, the fact you have people like Holliday, who just carries a gun by default, makes a society violent, because you have a lot of random citizens carrying deadly weapons and they are ready (and it seems even proud) to use them.
Last but not least, I honestly do not believe there are "bad" and "good" guys. The best people in the world do stupid things at times. The point is that the less violent is a society, the better for everybody - and the US is a very violent society. I acknowledge there are some areas where you NEED a gun, but that is sick and should be addressed ASAP.