sudo: effective uid is not 0, is sudo installed setuid root?
For whatever reason, you have a sudo installed in /usr/local/bin (see the output of type). Did you install something with homebrew or another package manager?

To fix, run

/usr/bin/sudo mv /usr/local/bin/sudo /usr/local/bin/sudo-strange


or (if you want to get rid of it completely)

/usr/bin/sudo rm /usr/local/bin/sudo