Always "Resolving host" on initial connection until Wifi restart

Lots of questions about "resolving host" but I can't find any that deal specifically with initial connections. When I try to connect my Macbook (mid-2012 13 inch, Yosemite 10.10.3) to an already setup network for the first time of the day - e.g. when tethering to android or arriving at work - the browser belligerently sticks to "resolving host" until I switch wifi off and back on, despite ostensibly having a full connection wifi icon. Then the connection is fine. This happens pretty consistently. Any idea why?

I think on the same line as ryebread: in SystemPreferences->Network->WiFi chosen at the left side->Advanced->DNS tab: put in 8.8.8.8 8.8.4.4 with the plus sign then OK - Apply.