I don't want everything to be a cake walk, but I do want the abilities of the PCs to matter. And if everything is auto-scaled to the PCs, their abilities don't really matter.

Personally speaking, I think people take "challenge" as too much of a hard rule. Not every fight needs to be equally challenging! If some of them are easy and others are various degrees of challenging/deadly, that's fine. So the PCs found out they were facing magma trolls, prepared accordingly, and now they're facerolling them? Yes, that is ok, that's not a problem you need to solve - or should solve - by a retroactive "and the trolls had an ice drake in reserve!" Let them take the easy win, aim a bit tougher for the next arc, done.

The one case that becomes a problem is when a foe is supposed to have particular significance in the world and they blatantly don't live up to it. Like, "Grath the Executioner is the lone guardian of the gate to the netherworld - the last time someone got past him was a century ago" - and then it turns out that Grath goes down like a chump and everyone's wondering "how the hell did this guy survive a century of battles?" For that I'd recommend not introducing such setting-critical characters immediately, wait until you have a better idea what the right optimization level is.