One illustrative method disclosed includes, among other things, selectively forming a gate-to-source/drain (GSD) contact opening and a CB gate contact opening in at least one layer of insulating material and forming an initial gate-to-source/drain (GSD) contact structure and an initial CB gate contact structure in their respective openings, wherein an upper surface of each of the GSD contact structure and the CB gate contact structure is positioned at a first level, and performing a recess etching process on the initial GSD contact structure and the initial CB gate contact structure to form a recessed GSD contact structure and a recessed CB gate contact structure, wherein a recessed upper surface of each of these recessed contact structures is positioned at a second level that is below the first level.