In my experience, the main difficulty is identifying, classifying, and documenting the cookies that are used... and then updating the codebase so that they are only set once the visitor has opted in. This is especially difficult when Google Tag Manager is involved, and/or swathes of tracking scripts have recklessly been bundled in over the years.
Projects and services that tout "automatic cookie consent with minimal config" are extremely frustrating, because they hide the actual issue. Implementing a cookie consent UI is itself not a particularly difficult task.