I think a game with "soul" is a game for which it is prohibitively difficult to make a good AI.
Consider Dominions and FfH2. They're both great games, with a huge variety units, spells, effects, world spells, races, and flavor text. In particular, all of these little bits interact with each other in interesting and complex ways, and if you bring the wrong set of powers to a battle, you will be completely wiped out (e.g. a niefel giant vs light infantry, or a group of fire mages vs an unprepared niefel giant). Each race plays very differently, and it can feel like an entirely different game switching from EA Arco to LA Ermor, or from the Ljosalfar to the Infernals in FfH2.
Now consider Gal Civ. In terms of gameplay, races are only distinguished by the modifiers they get to certain operations (e.g. +20% missile attack, or +10% population growth). The technologies you can research change these modifiers slightly, and only rarely introduce actual new abilities. Combat barely changes through out the game, and the 3 different types of attacks might as well be labeled A, B, and C for all the color and unique properties that they have. So when you research the great new weapon at the end of the tech tree, your attack bonus for weapon A goes from 140% to 160%. Yay. This simplicity and boringness is nice though if you are trying to write an AI, since all you have to do is maximize the product of all the various modifiers. You don't have to worry about teleporting enslave squads and SC equipment and Horrors and miasma dominion and poison resistance and unrest causing rituals and so on.
If a game is filled with meaningful, interesting, and complex decisions, and the player constantly has to think, then I would say it has soul. If the player's decisions can be easily automated, then the game doesn't have soul.