Game Design: Character Depth through mechanics or written script?

We've been faced with the commandment from our 'marketing department' (they're not marketing department so much as media people) to make the characters deeper and give them more character in our current game.
We've taken several steps to improve depth of, and relation to, the characters. First of all, every character has eye contact with the player, which to me seems like an untested experiment, but that may be a good idea, it's not like I'm hesitating to try it out.
Second, we've decided to increase the amount of background story of the characters, which to me is a sin in game development, given that each word you tell decrease the characterization which is created through actual game mechanics or the player's gaming experience itself.

For example, a simple soldier in a game like X-com has no background story on him or her, except for the statistics he or she has when she is hired and his or her name (which admittedly, says a alot). However, as soon as that individual is given a player-invented name and makes it for the next rank, making him or her even more of an individual, the character's depth has increased vastly. If we now also, as a player, begin to fall into playing patterns, such as always equipping this character with a laser sniper rifle, since this character has good perceptive attributes, the character has grown from [name]+[attributes] to Lieutenant [Player given name] who is a specialist with a sniper rifle. Every mission this Lieutenant is sent on will further increase the depth of the character. Finally this may be Oleg, the Officer of Sniper Specialists to was the only survivor from the battle at the local Hospital, where he had to take down three of his mind-controlled subordinates, now moved to the frontier outpost charged with responsibility of taking out every single brainsucker coming close to the gates.

In order to go half way, we've come up with an idea which we'll try out: When the game begins and you've just met the character, he or she will be revealed briefly with shallow details of style, family and class. These details are then elaborated upon as the player improves the relationship variables related to this character, in several layers and levels. This story is however, strictly background material. No developer should tell the player a story - that's the player's job.

Oh and we've got a new (or really, it's our first) logotype. So we can now be corporate on your ass and send e-mails with predefined sig's.