It's not about first vs third party, or tracking or non-tracking cookies, or adverts.
Any data storage on the end user's device (cookies, local storage etc.) that is not strictly necessary to provide the service requires consent. So even basic and (relatively) privacy-friendly analytics cookies are covered by this.
When the new ePrivacy regulation is finally adopted[0] the rules will be relaxed a little to allow things like analytics cookies to be used without consent.
This is the full text of the law:
"Member States shall ensure that the storing of information, or the gaining of access to information already stored, in the terminal equipment of a subscriber or user is only allowed on condition that the subscriber or user concerned has given his or her consent, having been provided with clear and comprehensive information, in accordance with Directive 95/46/EC,[1] inter alia, about the purposes of the processing. This shall not prevent any technical storage or access for the sole purpose of carrying out the transmission of a communication over an electronic communications network, or as strictly necessary in order for the provider of an information society service explicitly requested by the subscriber or user to provide the service."
[0] it was originally going to be adopted in 2017/8 and come in to force a year or two later but that whole process has been a mess
[1] That's the Data Protection Directive, which has been repealed and replaced by the GDPR.