Their constructing the monument was something of a feat.
Their constructing of the monument was something of a feat.
As a native speaker , what sort of difference in meaning do you sense between the sentences , bearing in mind that the only difference is the adding of "of" to the second sentence ?
It's hard to answer this question due to the fact that a native speaker would not say either of your sentences.
I suggest using:
"Their construction of the monument was something of a feat."
As an American native English speaker, I perceive no difference in meaning between the two example sentences; however, without additional context justifying its inclusion (for instance, in the preceding paragraph), I would drop "Their" from either sentence; i. e.,
"Constructing the monument was something of a feat."
The only problem with either sentence is that "something of a feat" is a weak description. Constructing a backyard BBQ is "something of a feat." Constructing a monument is presumably something much more than that; for instance,
Constructing the monument was a considerable (or enormous, or magnificent) feat.
Construct takes an object, and gerunds can take objects. The monument is an object of constructing.
Their constructing the monument was something of a feat
You can use of X to explicitly provide the reason, purpose, or "destination" of many nouns. The monument is the "destination" or reason for the constructing. As gerunds are nouns this can be done with them as well.
Their constructing of the monument was something of a feat.
Both expressions are basically two paths that arrive at the same meaning.
If you wished to draw attention to the monument - i.e. if the act of constructing the monument is a feat and not just the act of constructing (without regard to what is being constructed) - then the second sentence would be better.
