I believe the first country to legalize Bitcoin would be Estonia as the government seem to be very crypto friendly. The next one I believe that would adopt crypto is China, though I think they would use their own crypto like NEO or Qtum. Switzerland too seems to be very friendly to crypto.
Ye right, about Estonia, probably because the parliament is short of getting money out of people. They want 21% tax money out of bitcoin trading (everything you make from selling and buying between cryptocurrencies, not exchanging from BTC to Euro).
I guess the first one to be actually will be Canada, as it tries to get Chinese miners to their side. They literally saw the potential of selling the electricity to miners.