Your DM is asking for details of the approach so they can determine what checks, if any, to ask for; as well as what the DCs should be.
The core issue here is that some skill checks are straightforward and some are circumstantial.
In your two examples, you have one straightforward check (Strength to move some barrels) and one circumstantial check (Deception to trick a clerk into giving you horses for free).
In general, a straightforward check is one where the details of the situation don't matter. Physical checks tend to be straightforward, because fewer things affect the circumstances of physical actions. E.g., the specifics of how you lift something heavy don't meaningfully change under different circumstances. Assuming you have sufficient training as reflected by your bonus, you're always going to be performing the action the same way; there aren't usually multiple techniques whose use will affect the situation.
On the other hand, a circumstantial check is one where the details of the situation matter very much. Social checks tend to be circumstantial, because social interactions depend on the PCs' approach. In other words, how you convince a clerk to give you horses will change based on things like whether you're actually town heroes, whether the clerk knows and cares that you're heroes, whether it's normal for heroes to be given horses, what the risk is to the clerk if they give away free horses, and so on. Relatedly, the checks involved will change depending on whether you're taking an aggressive approach (Intimidation), a subtle one (Deception), or a friendly one (Diplomacy). A high bonus will help your character identify these factors and address them convincingly (see below about how the DM should help you here), but ultimately it's up to the player to choose the final approach based on all the circumstances in play, and then to the DM to call for the appropriate check(s) based on that approach.
Another way to look at it is to consider whether the target of the check cares about the PC's approach. Physical checks often interact with objects, which typically don't care what the PC does. The barrel doesn't care if the PC lifts with their legs or not; the wall being climbed doesn't care if the PC uses pitons or not. That's what makes it straightforward.
With a social check, however, the target of the check is usually an NPC, who does care about the PC's approach. A clerk who gives away free horses could lose their job, or worse. There are multiple ways the PCs can handle the encounter - Deception is one way, but if the approach the PCs describe is aggressive, the DM can and should call for Intimidation instead. Or if the PCs do a few knowledge-gathering checks beforehand to identify the best lie to tell, the DM may not call for any check at all because the PCs did their research. (Or may only call for the check to see if the PCs can tell the lie convincingly.) The way the PCs approach the interaction will change depending on the situation - that's what makes it circumstantial.
Physical checks can be circumstantial, but social checks are rarely straightforward.
For example, if a player wanted to lift heavy barrels containing an explosive rigged with a tilt fuze, I might ask for details about how they're doing so because it matters to both the check DC and the outcome of a success or failure. In this case, the barrel does care about the player's approach. If they're simply hefting the barrels without considering the fuze, the DC to lift might be low but the barrels will explode for sure. On the other hand, if the player gives details about how they're lifting the barrels to avoid tilting them, the DC to lift will be higher, but the barrels will be less likely to explode depending on the player's explanation.
However, there are very few social situations in which the details of the players' approach don't matter. If the players offer the clerk a bribe that mitigates the risk of losing their job, the Deception DC will be lower. On the other hand, if horses are not normally given away for free to anyone, town heroes or not, then as the GM I might not allow the Deception check because the players' story doesn't fit the circumstances. If the PCs try that story anyway, get rebuffed, and then threaten the clerk, now the situation calls for an Intimidate check.
This is not to say that social checks can never be straightforward, but in my experience, it's so rare that I couldn't even think of a good example.
The DM needs to work with you
This is the part where your group needs to sit down and have a discussion. Be careful about how you approach this so it doesn't come across as you players "against" your DM or as though you're trying to bully your DM into letting you use Charisma skills in ways that don't make sense. What you want is for the whole table - which includes your DM - to agree on how to handle skill checks and social situations so that everyone is on the same page and having fun.
As a group, lay out some ground rules about how much detail is needed for circumstantial checks, especially in cases where the player's skill is wildly mismatched from the character's. (Note that this applies in both directions: if a wizard with a negative Strength is played by a professional weightlifter, they shouldn't benefit from the pro lifter's knowledge to move those explosive barrels.)
In my groups, we typically agree on the following:
As a GM, I promise to:
- Provide as much relevant context about a social situation as possible before calling for a check, to allow the players to pick an appropriate approach
- Add additional context if it's clear that the players are missing something important which their characters would be aware of
- Give prompts or hints if my own expertise outweighs the player's
- Adjust the check DC, and what check or checks I call for, depending on the details of the players' approach
- Expect and accept a reasonable level of detail for the situation at hand (see @DarthPseudonym's comment below).
In exchange, I ask my players to:
- Make a good-faith effort to provide reasonable detail based on the situation
- Ask questions if they feel like they don't have enough information to select a good approach
- Be willing to explore the RP opportunities that come from social checks, successful or not.
An agreement like this will help players develop interesting premises for social skills, make circumstantial checks of any kind feel more doable, and preserve the realism of the game world and the social interactions between PCs and NPCs.