The error isn’t complaining about /sbin/init but about /usr/libexec/podman/catatonit, which points to /usr/libexec/catatonit/catatonit. The latter is provided by the catatonit package which is presumably not installed on your system (it’s only a weak dependency for podman).
On Fedora,
sudo dnf install catatonit
should fix things (but the package should be installed for you if you install podman).
On Debian, you’re running into #971815; you’ll have to either wait for a fix for that bug, or provide your own container init. One method is
sudo ln -sf /usr/bin/docker-init /usr/libexec/podman/catatonit
or configure podman to use docker-init directly instead of catatonit (in ~/.config/containers/containers.conf).
[containers] init_path="/usr/bin/docker-init"