So what type of tires are you rotating and do you mean the pump doesn't turn on or just that you don't have to slow down?
I have a compressor similar to the one you listed but with only a 20 gallon tank. Doing tire changes on smaller cars (ie 4-5 lugs that come off easily once broken) it never had an issue. It probably did cycle once or so during the job but I always had at least 90 psi at the tool. As a short term deal I'm using a small 4gallon 4CFM@90 psi compressor. It also really don't have an issue with tire changes. Yes, it generally cycles once per wheel. However, I'm just not pulling lug nuts so fast that it can't keep up. It also only takes 15 seconds to go from 100 (pump turns on) to 120 psi (full). If I were doing truck tires then the 4 gallon tank may not be enough to work without ever slowing down.
A big issue I see with the compressor you listed is it's just too close in price to a 3hp, 60 gallon, 240V model (Lowes has those starting around $450). At the same time, that compressor isn't much more powerful than the 8-10 gallon HF models like this one ($100+ cost of oil and other required accessories, coupon code came from following your link, coupon 51429128)
http://www.harborfreight.com/8-gal-2-HP-125-PSI-Oil-Lube-Air-Compressor-68740.html
Based on the specs and my experience using an IR 231 impact wrench, you should get about 8-10 lug nuts before the pump cycles. It should take about 30 seconds to refill the air. So unless you are moving between tires faster 30 seconds I would think that the $100 model would be sufficient for your needs.
The larger compressor should have no trouble.