There seems to be a lot of novice users here talking about this issue as well, so I'll go through what works for me step by step.
I have been having the same problem on and off. Sometimes when I reboot this happens and sometimes it doesn't, but it's annoying as I prefer to use Safari, especially as it has everything from my keychain across multiple devices.
First of all Mac apps don't use nslookup or dig, sure they are available to use at the command line for your convenience, but safari doesn't use either of them.
Mac apps use a process called mDNSResponder
try this:
sh-3.2# ps -ef|grep mDNS|grep -v grep
And you should see something like the following output:
65 898 1 0 12:10PM ?? 0:00.36 /usr/sbin/mDNSResponder
0 988 881 0 12:15PM ttys000 0:00.03 mDNSResponderHelper
So there are two process running that Mac apps need to translate website names to IP addresses.
Now this is just my theory, which I have tested and seems to hold up, but if those processes start before networking has loaded properly, you get this problem in Safari.
What fixes it for me is kicking those processes and there are two ways to do it...
from the list above, the process ID's are 898 and 988 so here are the commands:
sh-3.2# kill 898
sh-3.2# kill 988
this is the lazy way to do it and it works just fine, you can confirm the processes are running again with:
sh-3.2# ps -ef |grep mDNS|grep -v grep
65 1253 1 0 12:39PM ?? 0:00.11 /usr/sbin/mDNSResponder
0 1254 1 0 12:39PM ?? 0:00.03 /usr/sbin/mDNSResponderHelper
and note the process ID's have changed to 1253 and 1254 on my machine.
Note: If you send a kill -9 to these process then mDNSResponder will restart but mDNSResponderHelper will not. You will have to start it in the background.
####QUICK FIX RIGHT HERE###
For your convenience, here is a single command to do all of that so you don't have to worry about all of those words and stuff, just C&P the below and then start Safari

sudo ps -ef|grep mDNSResponder|grep -v grep|awk '{print $2}'|xargs kill
Before the purists get on my case, you can also restart these process with launchctl and here is how you do that:
sh-3.2# launchctl unload -w /System/Library/LaunchDaemons/com.apple.mDNSResponder.plist
and then reload it again with:
sh-3.2# launchctl load -w /System/Library/LaunchDaemons/com.apple.mDNSResponder.plist
Hope this helps someone that was as frustrated as me and unable to find a fix out there that worked
