I am currently living in an Asian culture where taste buds are apparently more delicate. Many first-time tasters of fudge almost gag due to the overwhelming sweetness of fudge. I have searched in vain for recipes that reduce the richness of fudge in order to make it more palatable. Any suggestions as to how to reduce sweetness in fudge but still allow it to be fudge?
Traditional "fudge" gets its structure primarily from the sugar, which forms fine crystals; the texture of fudge is a stiff suspension of the sugar in the fat. So simply reducing the proportion of sugar will mess up the texture, as GdD alluded to.
But fudge isn't the only thickened-fat confection out there! One dish that immediately comes to my mind is sesame halwa, which uses the sesame particles in the same way fudge uses the sugar particles. Nut butters generally have a similar suspension (if you've had "natural" peanut butter without hydrogenated oils, or tahini or sesame sauce for that matter, think of the extra-thick layer that forms when it hasn't been stirred).
So I think you could temper the sweetness by combining a fudge recipe with something like sesame halwa, or by adding peanut flour as a substitute for some of the sugar. If you use light-colored peanut flour I don't think it would even affect the taste too much (other than reducing the sweetness, of course).
You can't make fudge less fudgy. Fudge is a concentrated mass of butter, sugar and milk, if you change the balance to reduce sweetness it will be too buttery, if you reduce the butter it's too sweet. It's an intense flavor that isn't to everyone's liking even in areas where it's widely available.
If you want to introduce people to the flavor without them being overwhelmed use small amounts rather than big chunks, preferably used as a feature in a different dessert with less intense flavors.
I'm not sure this will temper the sweetness enough for your audience, but you can bring it down a bit by using dark chocolate and putting stuff in your fudge. I haven't tried this exact recipe but it's fairly close to my generic fudge recipe, except that I just eyeball the quantities of whatever I want to mix in: dark chocolate, pistachios, and candied ginger.
Another option is to try a non-chocolate fudge. Matcha green tea fudge seems to be popular, and it might be a more familiar flavor for your tasters.
Have you considered different forms of sugar like pure glucose? You could also add in some maltodextrin which is a kind of sugar, it's used in sugar-free candy/chocolate like Russell Stover brand.
I agree with the other answers that say the fudge gets its consistency from the sugar. You're going to need to substitute some of the sugar with something of similar consistency. This will be a small experiment.