I can reproduce this behavior if DNS is configured, but the system's regular, old fashioned hostname(1) does not match the Bonjour "LocalHostName". To illustrate:

My DNS config comes from DHCP, but that's not totally relevant here. Notably, I also have a search domain (mine is "dl", yours is "Home")

[~] % ipconfig getpacket en0 | grep domain
domain_name_server (ip_mult): {192.168.5.2}
domain_name (string): dl
domain_search (dns_namelist): {dl}

This DNS config is used for both legacy unix APIs...

[~] % cat /etc/resolv.conf | grep -v #
search dl
nameserver 192.168.5.2

... and also OS X's networking frameworks

[~] % scutil --dns 
DNS configuration

resolver #1
  search domain[0] : dl
  nameserver[0] : 192.168.5.2
  if_index : 4 (en0)
  flags    : Request A records
  reach    : Reachable,Directly Reachable Address

DNS configuration (for scoped queries)

resolver #1
  search domain[0] : dl
  nameserver[0] : 192.168.5.2
  if_index : 4 (en0)
  flags    : Scoped, Request A records
  reach    : Reachable,Directly Reachable Address

HostName / hostname is foci.local

[~] % scutil --get HostName
foci.local
[~] % hostname
foci.local

LocalHostName is something else, not "foci". These can also be configured in the Sharing prefpane.

[~] % scutil --get LocalHostName
blamp

getfqdn() stalls

[~] % time python -c 'import socket; print socket.getfqdn()'
foci.local
python -c 'import socket; print socket.getfqdn()'  0.02s user 0.01s system 0% cpu 5.117 total

if I fix LocalHostName...

[~] % sudo scutil --set LocalHostName foci                  

getfqdn is quick again!

[~] % time python -c 'import socket; print socket.getfqdn()'
foci.local
python -c 'import socket; print socket.getfqdn()'  0.02s user 0.01s system 32% cpu 0.091 total

In summary, make sure LocalHostName and the host component of HostName are the same. If they aren't, change LocalHostName.