The key to doing this is an email provider that will let you do a catch all account. Every email that doesn’t match a known mailbox gets delivered to the catch all mailbox. This allows you to “create” new addresses with zero overhead by just typing in whatever you want when you are signing up for something (or speaking a brand new email out loud to a retail store employee or whatever).

Later on if you want to organize more or “unsubscribe” from an address you can go into your mail control panel and add clean server side filtering rules.

As for which service? It is difficult to find traditional mail providers that will let you do this. I’ve gotten a variety of excuses when I ask prospective providers: they want to monetize based on number of email addresses, are “afraid” of all the spam they imagine they will get, or it’s just too niche a feature to build into their web gui. I use a shared hosting provider (I don’t really use the web hosting itself, just the email).

I mean, consumer email providers don't allow this, but it's pretty table stakes from bring your own domain providers (Google Apps, Fastmail, Microsoft).

Both fastmail and protonmail offer 'masked emails' which will generate a random email address for you and link it to your email account automatically. If the address gets compromised you can block it easily.

Fastmail lets you send email from <arbitrary_string>@yourdomain.com.