> I also don't love enums for errors because it means adding any new error type will be a breaking change

You can annotate your error enum with #[non_exhaustive], then it will not be a breaking change if you add a new variant. Effectively, you enforce that anybody doing a match on the enum must implement the "default" case, i.e. that nothing matches.