@whitequark I've been able to do this just now:
podman run --rm -it --security-opt label=disable --user podman quay.io/podman/stable podman run -it --rm --user root registry.fedoraproject.org/fedora-toolbox
that's an image specifically built to use podman inside podman (or docker I guess?) and I'm running it as user and without --privileged and inside of it is a fedora toolbox and inside the fedora toolbox itself I was able to curl codeberg.org
This might be a good place to start from. Not sure what exactly makes the error about tun/tap not happen with this image, however