I have a stock NS Oscar and a Mazzer Mini. I'm looking to upgrade either of these to the next "tier", and I'm trying to figure out which should be replaced to improve shot quality. Should it be the grinder or machine, and why?

Definitely upgrade the Mini then upgrade the machine. With some finesse the Oscar is capable of making great espresso.

I faced a similar choice. I upgraded my Silvia to a Profitec Pro 700 first. My reasoning was not for improved shot quality but for ease of use. The Profitec allows me to steam and brew together, plumb and drain the machine, etc which has greatly improved my prep time and overall experience. Shortly thereafter I upgraded my grinder which has definitely improved my espresso quality, albeit in a subtle way.

If you're happy with the overall use of the Oscar, upgrade the grinder. If the Oscar is bothering you, upgrade the machine first.

1.Coffee
2. Barista knowledge/skill
3. Grinder
4. Machine

I rank these in order of what I think makes the biggest difference in a great or poor shot. If you are wanting to upgrade why not invest some time and money into your knowledge and skills? I think this is often overlooked. If you truly feel your setup is holding you back and not your abilities I would recommend upgrading your grinder then machine.