Since puppet uses the fqdn fact to determine which node it is running as, it may not be possible to run if it can’t be determined. Given what you’re describing, the simplest thing to debug is facter fqdn instead of your puppet command-line.
If the “several seconds” is very close to exactly 5 seconds, it’s very likely that your DNS configuration is broken with a single bad DNS server listed. What’s in /etc/resolv.conf? What happens if you run dig -x $HOSTIP $DNSSERVERIP with the first nameserver listed in resolv.conf?
If you look in facter/fqdn.rb you can see what exactly facter is trying to do to resolve the fqdn. In the version I have most handy it’s using facter/hostname.rb and facter/domainname.rb which call code from facter/util/resolution.rb.
Exactly what happens will depend on what version of facter you have, what OS, and possibly also what exactly you have installed. Calling /bin/hostname, uname (etc) and doing DNS lookups are all quite likely. You can always use strace -t facter fqdn to see what is taking the time (look for the gap in timestamps)
From everything you’ve described, it does sound like the problem is that puppet/facter really wants to have a domain name and you don’t have one, you just have a naked hostname.
Adding domain example.com to /etc/resolv.conf should do the trick. Running hostname foo.example.com should also do the trick (but will need to be re-applied). Permanent solutions depend on the exact OS setup.