The data controller is responsible for GDPR compliance. For embedded content, case law such as the Fashion ID case indicates a joint controllership where both the controller of the embedding page and the controller of the embedded content are controllers. However, one can only be controller for processing activities where one has influence on the means and purposes of processing. So the controller of the embedding page is a controller with respect to the act of embedding (with purposes like showing a video), but they wouldn't be a controller for subsequent processing by that embedded content (with purposes like tracking people across the web).
For determining who is a controller, it is not too helpful to look at which servers sent which HTTP headers. Instead, look at which processing activities occur, for what purposes that processing is carried out, and who had input to determining these purposes. Those (natural or legal) persons are data controllers and are therefore responsible for compliance.
What does this mean for the example of embedding a Youtube video, Tweet, or Like button?
The controller of the embedding page needs a legal basis for sharing visitor's personal data with the embed provider. Such a sharing is inevitable due to the embedding, regardless of whether cookies are involved. Typically, the legal basis used here would be consent: in place of the embed, a placeholder is shown that lets visitors opt in to loading the content. In some cases, a legitimate interest argument might also work.
The joint controllers can divide up compliance obligations among themselves. For example, the provider of the embed content could likely require embedders to collect necessary consents prior to embedding (Twitter has similar terms). However, this would be risky for the controller because controllers shall be able to demonstrate that valid consent was actually given.
So in conclusion, I largely agree with your analysis that the provider of the embedded content should consider cookie consent. With two caveats: the controllers might have an agreement that moves this responsibility to the embedder, and the embedding data controller might need consent to embed the content in the first place.