The service cannot be dependent on the acceptance of third party cookies, no. That is, the service provided to those that reject third party cookies cannot be worse (slower or incomplete, for example) compared to the visitors who accept cookies.
So you can supply an ad supported version and a paid version without ads, but you cannot require that those that choose the ad supported version must accept tracking ads.