Help on understanding frosting
Based on your description, I am 99.999...% certain that your wife likes the good ol' American-style Wilton buttercream. It's literally butter and powdered sugar whipped together, with a little milk, salt, and flavoring to taste. Thick, heavy, sticky, grainy and pasty are all good descriptors. 

For what you like-- the most likely possibility, since this sounds like a storebought cake(?), is that you're just getting an American buttercream with corn syrup and vegetable shortening used instead of some or all of the butter, basically a cool whip without that signature cool whip taste.

There are a lot of more interesting options though. Italian and Swiss meringues are both less sweet than American buttercream and are not grainy at all, but since they only contain egg whites, butter, and sugar, might lack a noticeable cream taste. Or noticeable taste of any kind. French buttercream is similar, but replaces some or all of the egg whites with yolks. It has a richer taste, but... well, eggs don't taste like cream. The European buttercreams are higher in fat proportionately, and I'd describe them all as a little slick and quick to melt, but they seem to coat your mouth a bit. But in a recognizable, buttery way, which is very different from storebought frostings.

Since your frosting has a pudding-like consistency, and a creamy taste, then my guess, or rather recommendation, is an ermine frosting, or perhaps a German buttercream. Both of these start with a sort of pudding which is then beaten with butter to make a frosting, lending them a dense but fluffy texture. Both of them offer custom sweetness-- especially ermine buttercream. You can make that with no sugar at all if you want to. Ermine buttercream starts with a cooked starch and milk pudding base, and German buttercream begins with a pastry cream base -- cooked starch, milk, and egg yolks; Sugar to taste for both, but in the case of the German buttercream, the less sugar you use, the more likely you'll end up with scrambled egg bits. 

Overall they have the capacity to be the least sweet of all frostings, and because of the higher liquid and starch content, they're actually a little lower in fat proportionately. While less sweet to taste, they're still just as high in carbs due to the starch. They have a very thick, sticky, but smooth texture, without necessarily being "rich" as these things go.

The fact that you're using a chocolate frosting as a frame of reference does make it more complicated. As mentioned in a comment, you could be looking at a ganache, or a glaze made with cocoa powder or syrup. When you say pudding, I think of instant jello pudding. If that's what you meant, then again, I think you're looking for ermine or German buttercream. 

However, be aware that vegetable shortening-based frostings are much, much more common, as they are cheaper, less labor-intensive, and easier to make. If you aren't familiar with the more traditional options, I could imagine describing them as "pudding-like."