Sanity and smoke tests are used sometimes interchangeably (wrongly). Even I sometimes fall in that mistake.
They are not specifically related with automated “tests” (i.e. checks), although many times they’re supported as automated “tests”. Why? Because it’s the most expedite way of validating if you broke anything.
Normally I would complement these automated checks with some exploratory testing on top of it, so you can find something that goes beyond the strict and well delimited scope of automated tests.
However, if your basic automated tests fail then probably you need to have a look at them and check what is wrong (it can also be the automated check itself because your system now works in a different way).
I also agree with @juanalvarezarquillos in the sense that you need to “set your goal”; I would rephrase it as assessing your risks and mitigate them properly.
If you have a high-level risk, you should start by looking at that first.
Smoke tests are used to find out if your build is stable enough to be tested exhaustively in a proper environment. Does your software start and keeps running? Is the web server and all remaining services up as expected? If it does reach the minimums, then it can’t be further tested, and development needs to look at immediately.
On the other hand, sanity tests are performed after basic smoke tests. The purpose of sanity tests is to check that changes that were introduced in the build don’t affect the core features of the system.
You can do sanity tests using whatever approach you want (manual scripts, automated scripts, exploratory testing). I’d recommend having a set of automated checks that go over the main features of the AUT/SUT, to give you a quick feedback.
Are smoke and/or sanity tests regression tests? Well, sanity tests for sure and, IMO, smoke tests also as they validate the system based on its architecture, which is consequence of non-functional requirements implemented in previous versions.
Concerning your two questions:
Should we do Smoke testing or Sanity testing on a newly introduced feature in a stable Build?
Is it best to do Sanity or Smoke testing when the build is unstable?
you should do both. Smoke tests should be the ones you or the machine will perform for you. Having a good set of smoke tests can evaluate the stability of it. As more you may find in the advance about the stability of the SUT, better, as it will avoid unnecessary works afterwards.
If smoke tests passed, then you can perform sanity tests and all the regression tests (start with the automated "ones” - i.e. automated scripts/checks). Probably you have to decide which regression tests to perform…and here comes risk assessment: if you have to choose, start with by addressing the higher risks in the context of your build/release