OK, found what the issue was. The problem was that my phone's screen was going blank after the normal boot screen, so I couldn't see when it gets turned off. I was simply pressing the Vol Up + Power for too long, so it would go into full reboot. I just measured the amount of time it was taking to do this (was ~12 seconds). So I pressed Vol Up + Power for ~10 secs, then released those and pressed Vol Down. That finally brought me into Fastboot.
I could have probably gotten the same result by pressing Vol Down + Power, however, the phone screen was blank all the time, so it was difficult to understand when I should have released the Power button to let it go into Fastboot.